# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
44569 | 2018-04-03T10:40:40 Z | ssnsarang2023 | Zagonetka (COI18_zagonetka) | C++17 | 108 ms | 512 KB |
#define debug #include <bits/stdc++.h> using namespace std; typedef long long ll; typedef unsigned long long ull; typedef pair<int, int> ii; #define SZ(x) ((int)x.size()) int n, a[105], b[105], pos[105], deg[105]; bool adj[105][105]; bool ask(vector<int> &lst) { queue<int> q; int idx = 0; for (int i = 1; i <= n; ++i) { b[i] = a[i]; deg[i] = 0; } for (auto &u : lst) { for (auto &v : lst) { deg[v] += adj[u][v]; } } vector<int> val; for (auto &v : lst) { val.push_back(b[v]); if (!deg[v]) { q.push(v); } } sort(val.begin(), val.end()); idx = 0; while (SZ(q)) { int u = q.front(); q.pop(); b[u] = val[idx++]; for (auto &v : lst) { if (!deg[v] || !adj[u][v]) continue; --deg[v]; if (!deg[v]) { q.push(v); } } } for (auto &v : lst) { if (deg[v]) { return 1; } } printf("query "); for (int i = 1; i <= n; ++i) { printf("%d ", b[i]); } fflush(stdout); int re = 0; scanf("%d", &re); return re; } int main() { scanf("%d", &n); for (int i = 1; i <= n; ++i) { scanf("%d", &a[i]); pos[a[i]] = i; } for (int i = 1; i < n; ++i) { for (int j = 1; j <= n - i; ++j) { int x = pos[j], y = pos[j + i]; vector<int> lst; for (int k = 1; k <= n; ++k) { if (j <= a[k] && a[k] <= j + i) { lst.push_back(k); } } adj[y][x] = 1; adj[x][y] = !ask(lst); adj[y][x] = 0; } } set<int> q; fill(deg + 1, deg + n + 1, 0); for (int i = 1; i <= n; ++i) { for (int j = 1; j <= n; ++j) { if (adj[i][j]) { ++deg[j]; } } } for (int i = 1; i <= n; ++i) { if (!deg[i]) { q.insert(i); } } int idx = 0; while (SZ(q)) { int u = *q.begin(); q.erase(q.begin()); a[u] = ++idx; for (int v = 1; v <= n; ++v) { if (!adj[u][v]) continue; --deg[v]; if (!deg[v]) { q.insert(v); } } } fill(deg + 1, deg + n + 1, 0); for (int i = 1; i <= n; ++i) { for (int j = i + 1; j <= n; ++j) { swap(adj[i][j], adj[j][i]); } } for (int i = 1; i <= n; ++i) { for (int j = 1; j <= n; ++j) { if (adj[i][j]) { ++deg[j]; } } } for (int i = 1; i <= n; ++i) { if (!deg[i]) { q.insert(i); } } idx = n + 1; while (SZ(q)) { int u = *q.begin(); q.erase(q.begin()); b[u] = --idx; for (int v = 1; v <= n; ++v) { if (!adj[u][v]) continue; --deg[v]; if (!deg[v]) { q.insert(v); } } } printf("end\n"); for (int i = 1; i <= n; ++i) { printf("%d ", a[i]); } printf("\n"); for (int i = 1; i <= n; ++i) { printf("%d ", b[i]); } fflush(stdout); return 0; }
Compilation message
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Incorrect | 2 ms | 248 KB | Output isn't correct |
2 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Incorrect | 17 ms | 384 KB | Output isn't correct |
2 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Incorrect | 2 ms | 384 KB | Output isn't correct |
2 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Incorrect | 108 ms | 512 KB | Output isn't correct |
2 | Halted | 0 ms | 0 KB | - |