QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#180011 | #1464. Interactive Algorithm | FISHER_ | WA | 0ms | 3892kb | C++14 | 2.2kb | 2023-09-15 14:35:24 | 2023-09-15 14:35:24 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
const int maxn = 400;
int n;
int q[maxn + 5];
int query() {
printf("? ");
for (int i = 1; i <= n; i++) printf("%d ", q[i]);
puts(""), fflush(stdout);
int rs;
scanf("%d", &rs);
return rs;
}
void answer() {
printf("! ");
for (int i = 1; i <= n; i++) printf("%d ", q[i]);
puts(""), fflush(stdout);
}
bool e1[maxn + 5], e2[maxn + 5];
void c3(int v1, int v2, int v3, bool& a1, bool& a2, bool& a3) {
int tp = 3;
for (int i = 1; i <= n; i++)
if (i != v1 && i != v2 && i != v3) q[++tp] = i;
q[1] = v1, q[2] = v2, q[3] = v3;
int d1 = query();
swap(q[1], q[2]);
d1 -= query();
q[1] = v1, q[2] = v3, q[3] = v2;
int d2 = query();
swap(q[1], q[2]);
d2 -= query();
if (d1 > 0) a2 = 1, a1 = 1 - d2;
else if (d1 < 0) a3 = 1, a1 = -d2;
else {
if (d2 > 0) a2 = a3 = 1;
else if (d2 < 0) a1 = 1;
}
}
int queryd(int r, int d) {
const int l = 2;
int tp = 0, rs = 0;
int R = (r - l + 1) % d;
int pos = (R & 1) ? r - R + 1 : l;
for (int i = 1; i <= d; i++) {
if ((i ^ R) & 1) {
for (; pos <= r; pos += d) q[++tp] = pos;
pos -= d;
} else {
for (; pos >= l; pos -= d) q[++tp] = pos;
pos += d;
}
if (i < d) rs += e2[pos++];
}
q[++tp] = 1, rs += e1[pos];
if (r < n) {
q[++tp] = r + 1, rs += e1[r + 1];
for (int i = r + 2; i <= n; i++) q[++tp] = i, rs += e2[i - 1];
}
return query() - rs;
}
int to[maxn + 5];
int deg[maxn + 5];
inline void addE(int u, int v) {
deg[u]++, deg[v]++;
to[u] ^= v, to[v] ^= u;
}
int main() {
scanf("%d", &n);
if (n == 2) {
q[1] = 1, q[2] = 2;
return answer(), 0;
}
for (int i = 2; i < n; i++) c3(1, i, i + 1, e1[i], e2[i], e1[i + 1]);
e2[1] = e1[2];
for (int i = 2; i <= n; i++)
if (e1[i]) addE(1, i);
for (int i = 2; i < n; i++)
if (e2[i]) addE(i, i + 1);
for (int i = 2; i < n; i++) {
int r = i + 1, v = 0, mx = queryd(n, i);
while (v < mx) {
for (int j = 8; ~j; j--)
if (int nr = r + (1 << j); nr <= n && queryd(nr, i) == v) r = nr;
v++, addE(r, r - i);
}
}
int u;
for (int i = 1; i <= n; i++)
if (deg[i] == 1) { u = i; break; }
for (int i = 1, lst = 0; i <= n; i++) {
q[i] = u;
int t = lst;
lst = u, u = to[u] ^ t;
}
answer();
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 0
Wrong Answer
time: 0ms
memory: 3892kb
input:
5 1 1 1 1 3 2 2 1 1 2 2 2 1 1 2 2 2 2
output:
? 1 2 3 4 5 ? 2 1 3 4 5 ? 1 3 2 4 5 ? 3 1 2 4 5 ? 1 3 4 2 5 ? 3 1 4 2 5 ? 1 4 3 2 5 ? 4 1 3 2 5 ? 1 4 5 2 3 ? 4 1 5 2 3 ? 1 5 4 2 3 ? 5 1 4 2 3 ? 2 4 5 3 1 ? 2 4 5 3 1 ? 4 2 3 1 5 ? 5 2 3 4 1 ? 5 2 3 4 1 ? 2 3 4 5 1 ! 5 1 7 1 5
result:
wrong output format Unexpected end of file - int32 expected