QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#741723#9432. PermutationYansuan_HClRE 0ms0kbC++143.2kb2024-11-13 15:05:112024-11-13 15:05:11

Judging History

你现在查看的是最新测评结果

  • [2024-11-13 15:05:11]
  • 评测
  • 测评结果:RE
  • 用时:0ms
  • 内存:0kb
  • [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

result: