# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
44561 | ssnsarang2023 | Zagonetka (COI18_zagonetka) | C++17 | 296 ms | 480 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#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)
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |