Submission #44561

#TimeUsernameProblemLanguageResultExecution timeMemory
44561ssnsarang2023Zagonetka (COI18_zagonetka)C++17
0 / 100
296 ms480 KiB
#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], topo[105], n_topo; bool adj[105][105]; bool ask() { queue<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.push(i); } } n_topo = 0; while (SZ(q)) { int u = q.front(); q.pop(); topo[++n_topo] = u; for (int v = 1; v <= n; ++v) { if (!adj[u][v]) continue; --deg[v]; if (!deg[v]) { q.push(v); } } } for (int i = 1; i <= n; ++i) { b[topo[i]] = i; } 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 j = 1; j < i; ++j) { bool re = a[j] < a[i]; if (re) { adj[j][i] = 1; } else { adj[i][j] = 1; } } } for (int i = 1; i <= n; ++i) { for (int j = 1; j <= n - i; ++j) { int x = pos[j], y = pos[j + i]; adj[x][y] = 0, adj[y][x] = 1; bool re = ask(); adj[y][x] = 0; if (!re) { adj[x][y] = 1; } } } 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 = 1; 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 = 1; j <= n; ++j) { if (adj[i][j]) { ++deg[i]; } } } for (int i = 1; i <= n; ++i) { if (!deg[i]) { q.insert(i); } } idx = n; while (SZ(q)) { int u = *q.begin(); q.erase(q.begin()); b[u] = idx--; for (int v = 1; v <= n; ++v) { if (!adj[v][u]) 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 (stderr)

zagonetka.cpp: In function 'bool ask()':
zagonetka.cpp:51:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d", &re);
     ~~~~~^~~~~~~~~~~
zagonetka.cpp: In function 'int main()':
zagonetka.cpp:56:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d", &n);
     ~~~~~^~~~~~~~~~
zagonetka.cpp:58:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d", &a[i]);
         ~~~~~^~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...