#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; } |
English