QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#741723 | #9432. Permutation | Yansuan_HCl | RE | 0ms | 0kb | C++14 | 3.2kb | 2024-11-13 15:05:11 | 2024-11-13 15:05:11 |
answer
#include <bits/stdc++.h>
#define ms(x, v) memset(x, v, sizeof(x))
#define il __attribute__((always_inline)) static
#define U(i,l,r) for(int i(l),END##i(r);i<=END##i;++i)
#define D(i,r,l) for(int i(r),END##i(l);i>=END##i;--i)
using namespace std;
using ll = long long;
#define IC isdigit(c)
#define GC c=getchar()
void rd(auto &x) { x = 0; char GC; bool f = 0;
for (; !IC; GC) f |= c == '-';
for (; IC; GC) x = x * 10 + c - 48;
if (f) x = -x;
}
void rd(auto &x, auto &...y) { rd(x); rd(y...); }
#define meow(...) fprintf(stderr, __VA_ARGS__)
#define Assert(e, v) if (!(e)) { meow("AF@%d\n", __LINE__ ); exit(v); }
#define vc vector
#define eb emplace_back
#define pb push_back
const int N = 1003;
int n, a[N], p[N];
int q[N];
int ans[N], ansp[N];
int ask() {
printf("0");
U (i, 1, n) printf(" %d", q[i]);
puts(""); fflush(stdout);
int x; rd(x);
return x;
}
//int ask() {
// int cnt = 0;
// U (i, 1, n) if (q[i] == ans[i]) ++cnt;
// return cnt;
//}
void report() {
printf("1");
U (i, 1, n) printf(" %d", p[i]);
puts(""); fflush(stdout);
U (i, 1, n) assert(p[i] == ans[i]);
exit(0);
}
mt19937 rng(114514);
int b[N];
void solve(int l, int r) {
if (l == r) { p[l] = a[l]; return; }
shuffle(a + l, a + r + 1, rng);
U (i, 1, n) q[i] = a[l];
int mid((l + r) >> 1), x = l, y = mid + 1;
for (int i = l, j; i <= r; i = j + 1) {
j = i + 1; int las = 1;
do {
if (j > r) break;
U (k, l, mid) q[k] = a[i];
U (k, mid + 1, r) q[k] = a[j];
las = ask();
} while ((las == 1) && ++j);
if (j > r) {
// 要么 i 在左边,剩下的全在右边
// 要么 i 在右边,剩下的全在左边
if (i == r - 1) {
assert(i != l); // 要么两个都对,要么两个都不对
if (x + 1 == mid) {
b[x++] = a[i];
b[x++] = a[i + 1];
} else if (y + 1 == r) {
b[y++] = a[i];
b[y++] = a[i + 1];
} else {
if (x != l) {
U (k, l, mid) q[k] = b[l];
U (k, mid + 1, r) q[k] = a[i];
las = ask();
if (las == 1) {
b[x++] = a[i];
b[y++] = a[i + 1];
} else {
assert(las == 2);
b[y++] = a[i];
b[x++] = a[i + 1];
}
} else {
assert(y > mid + 1);
U (k, l, mid) q[k] = a[i];
U (k, mid + 1, r) q[k] = b[mid + 1];
las = ask();
if (las == 1) {
b[y++] = a[i];
b[x++] = a[i + 1];
} else {
assert(las == 2);
b[y++] = a[i + 1];
b[x++] = a[i];
}
}
}
} else {
if (y == r + 1) {
U (k, i, j - 1) b[x++] = a[k];
} else {
U (k, i, j - 1) b[y++] = a[k];
}
}
} else if (las == 0) {
// i 在右边
b[y++] = a[i];
b[x++] = a[j];
U (k, i + 1, j - 1) b[y++] = a[k];
} else if (las == 2) {
// i 在左边
b[x++] = a[i];
b[y++] = a[j];
U (k, i + 1, j - 1) b[x++] = a[k];
}
}
assert(x == mid + 1);
assert(y == r + 1);
U (i, l, r) a[i] = b[i];
// U (i, l, mid) assert(ansp[a[i]] <= mid);
// U (i, mid + 1, r) assert(ansp[a[i]] > mid);
solve(l, mid);
solve(mid + 1, r);
}
int main() {
// freopen("ava.in", "r", stdin);
rd(n);
// U (i, 1, n) rd(ans[i]), ansp[ans[i]] = i;
U (i, 1, n) a[i] = i;
solve(1, n);
report();
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 0
Runtime Error
input:
5 1 0 1 0 2 0
output:
0 1 1 1 5 5 0 1 1 1 2 2 0 4 4 4 3 3 0 2 2 3 2 2 0 3 4 3 3 3 0 5 5 5 5 1 1 3 4 2 1 5