QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#740880#9432. PermutationYansuan_HClRE 1ms3888kbC++142.3kb2024-11-13 12:03:192024-11-13 12:03:20

Judging History

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

  • [2024-11-13 12:03:20]
  • 评测
  • 测评结果:RE
  • 用时:1ms
  • 内存:3888kb
  • [2024-11-13 12:03:19]
  • 提交

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 ask() {
	printf("0");
	U (i, 1, n) printf(" %d", q[i]);
	puts(""); fflush(stdout);
	int x; rd(x);
	return x;
}
void report() {
	printf("1");
	U (i, 1, n) printf(" %d", p[i]);
	puts(""); fflush(stdout);
	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 {
					assert(y + 1 == r);
					b[y++] = a[i];
					b[y++] = a[i];
				}
			} else {
				if (x == mid) {
					b[x++] = a[i];
					U (k, i + 1, j - 1) b[y++] = a[k];
				} else {
					b[y++] = a[i];
					U (k, i + 1, j - 1) b[x++] = 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];
		}
	}
	
	U (i, l, r) a[i] = b[i];
	solve(l, mid);
	solve(mid + 1, r);
}

int main() {
	rd(n);
	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: 100
Accepted
time: 1ms
memory: 3888kb

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:

ok Accepted

Test #2:

score: -100
Runtime Error

input:

1000
0
0
0
2
1
0
1
0
0
2
0
1
1
0
1
0
1
0
2
1
0
0
1
2
0
2
2
2
1
2
1
0
0
1
2
0
0
1
1
1
0
2
0
1
2
1
0
1
2
1
1
0
2
1
1
2
1
1
1
1
2
1
0
0
0
2
0
1
1
0
1
1
1
1
0
2
1
0
2
2
2
1
2
2
1
2
0
2
1
0
1
2
2
0
1
2
2
1
1
1
1
2
1
2
1
1
2
2
1
1
0
1
1
1
0
0
1
2
1
0
1
1
0
1
2
1
1
1
2
1
1
1
2
0
1
1
1
2
1
2
2
1
0
2
2
0
1
2...

output:

0 940 940 940 940 940 940 940 940 940 940 940 940 940 940 940 940 940 940 940 940 940 940 940 940 940 940 940 940 940 940 940 940 940 940 940 940 940 940 940 940 940 940 940 940 940 940 940 940 940 940 940 940 940 940 940 940 940 940 940 940 940 940 940 940 940 940 940 940 940 940 940 940 940 940 94...

result: