#include <iostream> #include <vector> #include <queue> namespace { using std::cin; using std::cout; using crosses_t = std::vector<size_t>; using lines_t = std::vector<crosses_t>; using ends_t = crosses_t; using counters_t = crosses_t; using queue_t = std::queue<size_t>; void count_bfs(lines_t const & lines, size_t line, counters_t & counters) { queue_t q; size_t u; q.push(line); while (!q.empty()) { u = q.front(); for (size_t l = 0; l < lines[u].size(); ++l) { if (counters[lines[u][l]] == 0 && lines[u][l] != line) { counters[lines[u][l]] = counters[u] + 1; q.push(lines[u][l]); } } q.pop(); } } } int main() { size_t n; cin >> n; lines_t lines(n); ends_t ends(n); for (size_t i = 0; i < n; ++i) { cin >> ends[i]; } for (size_t i = 0; i < n - 1; ++i) { for (size_t j = i + 1; j < n; ++j) { if (ends[i] > ends[j]) { lines[i].push_back(j); lines[j].push_back(i); } } } size_t line_result = 0; for (size_t i = 0; i < n; ++i) { line_result = 0; if (lines[i].size() > 0) { counters_t d(n, 0); count_bfs(lines, i, d); for (auto const & x : d) line_result += x; } cout << line_result << ' '; } cout << '\n'; return 0; }
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 | #include <iostream> #include <vector> #include <queue> namespace { using std::cin; using std::cout; using crosses_t = std::vector<size_t>; using lines_t = std::vector<crosses_t>; using ends_t = crosses_t; using counters_t = crosses_t; using queue_t = std::queue<size_t>; void count_bfs(lines_t const & lines, size_t line, counters_t & counters) { queue_t q; size_t u; q.push(line); while (!q.empty()) { u = q.front(); for (size_t l = 0; l < lines[u].size(); ++l) { if (counters[lines[u][l]] == 0 && lines[u][l] != line) { counters[lines[u][l]] = counters[u] + 1; q.push(lines[u][l]); } } q.pop(); } } } int main() { size_t n; cin >> n; lines_t lines(n); ends_t ends(n); for (size_t i = 0; i < n; ++i) { cin >> ends[i]; } for (size_t i = 0; i < n - 1; ++i) { for (size_t j = i + 1; j < n; ++j) { if (ends[i] > ends[j]) { lines[i].push_back(j); lines[j].push_back(i); } } } size_t line_result = 0; for (size_t i = 0; i < n; ++i) { line_result = 0; if (lines[i].size() > 0) { counters_t d(n, 0); count_bfs(lines, i, d); for (auto const & x : d) line_result += x; } cout << line_result << ' '; } cout << '\n'; return 0; } |