Submission #586981

#TimeUsernameProblemLanguageResultExecution timeMemory
586981MilosMilutinovicZagonetka (COI18_zagonetka)C++14
0 / 100
589 ms336 KiB
/** * author: wxhtzdy * created: 01.07.2022 07:54:35 **/ #include <bits/stdc++.h> using namespace std; int main() { ios::sync_with_stdio(false); cin.tie(0); int n; cin >> n; vector<int> p(n); for (int i = 0; i < n; i++) { cin >> p[i]; } auto Ask = [&](vector<int> q) { cout << "query "; for (int i = 0; i < n; i++) { cout << q[i] << " "; } cout << endl; int x; cin >> x; return x; }; vector<vector<bool>> f(n, vector<bool>(n, true)); for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) { if (i != j && p[i] < p[j]) { f[i][j] = false; } } } auto Valid = [&]() { vector<vector<int>> g(n); for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) { if (i != j && f[i][j]) { g[i].push_back(j); } } } vector<int> in(n); for (int i = 0; i < n; i++) { for (int j : g[i]) { in[j] += 1; } } vector<int> que; for (int i = 0; i < n; i++) { if (in[i] == 0) { que.push_back(i); } } for (int b = 0; b < (int) que.size(); b++) { int i = que[b]; for (int j : g[i]) { in[j] -= 1; if (in[j] == 0) { que.push_back(j); } } } reverse(que.begin(), que.end()); vector<int> q(n); for (int i = 0; i < n; i++) { q[que[i]] = i + 1; } return Ask(q); }; vector<vector<bool>> save(n, vector<bool>(n)); for (int it = 0; it < n * (n - 1) / 2; it++) { vector<vector<int>> g(n); for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) { if (i != j && f[i][j]) { g[i].push_back(j); } } } pair<int, int> p = {-1, -1}; for (int i = 0; i < n; i++) { vector<int> que(1, i); vector<bool> was(n); vector<bool> ok(n, true); was[i] = true; for (int b = 0; b < (int) que.size(); b++) { int x = que[b]; for (int j : g[x]) { if (!was[j]) { was[j] = true; que.push_back(j); } if (x != i) { ok[j] = false; } } } bool found = false; for (int j = 0; j < n; j++) { if (i != j && ok[j] && f[i][j]) { if (!save[i][j]) { p = make_pair(i, j); save[i][j] = true; found = true; break; } } } if (found) { break; } } if (p.first == -1) { break; } swap(f[p.first][p.second], f[p.second][p.first]); if (Valid()) { f[p.first][p.second] = f[p.second][p.first] = false; } else { swap(f[p.first][p.second], f[p.second][p.first]); } } vector<pair<int, int>> c; for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) { if (i != j && f[i][j]) { c.emplace_back(i, j); } } } cout << "end" << endl; vector<vector<int>> g(n); for (int i = 0; i < (int) c.size(); i++) { g[c[i].first].push_back(c[i].second); } vector<int> mn(n); { iota(mn.begin(), mn.end(), 0); vector<int> in(n); for (int i = 0; i < n; i++) { for (int j : g[i]) { in[j] += 1; } } vector<int> que; for (int i = 0; i < n; i++) { if (in[i] == 0) { que.push_back(i); } } for (int b = 0; b < (int) que.size(); b++) { int i = que[b]; for (int j : g[i]) { in[j] -= 1; if (in[j] == 0) { que.push_back(j); } } } reverse(que.begin(), que.end()); for (int i : que) { for (int j : g[i]) { mn[i] = min(mn[i], mn[j]); } } } { vector<int> ans(n, -1); vector<int> in(n); for (int i = 0; i < n; i++) { for (int j : g[i]) { in[j] += 1; } } set<pair<int, int>> que; for (int i = 0; i < n; i++) { if (in[i] == 0) { que.emplace(mn[i], i); } } vector<int> order; while (!que.empty()) { int i = prev(que.end())->second; que.erase(prev(que.end())); order.push_back(i); for (int j : g[i]) { in[j] -= 1; if (in[j] == 0) { que.emplace(mn[j], j); } } } reverse(order.begin(), order.end()); for (int i = 0; i < n; i++) { ans[order[i]] = i + 1; } for (int i = 0; i < n; i++) { cout << ans[i] << " "; } cout << endl; } { vector<int> ans(n, -1); vector<int> in(n); for (int i = 0; i < n; i++) { for (int j : g[i]) { in[j] += 1; } } set<pair<int, int>> que; for (int i = 0; i < n; i++) { if (in[i] == 0) { que.emplace(mn[i], i); } } vector<int> order; while (!que.empty()) { int i = que.begin()->second; que.erase(que.begin()); order.push_back(i); for (int j : g[i]) { in[j] -= 1; if (in[j] == 0) { que.emplace(mn[j], j); } } } reverse(order.begin(), order.end()); for (int i = 0; i < n; i++) { ans[order[i]] = i + 1; } for (int i = 0; i < n; i++) { cout << ans[i] << " "; } cout << endl; } return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...