QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#742192#9432. PermutationSktn0089WA 1ms7848kbC++142.0kb2024-11-13 16:03:342024-11-13 16:03:39

Judging History

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

  • [2024-11-13 16:03:39]
  • 评测
  • 测评结果:WA
  • 用时:1ms
  • 内存:7848kb
  • [2024-11-13 16:03:34]
  • 提交

answer

#include <bits/stdc++.h>
#define ll int
#define fi first
#define se second
#define mkp make_pair
#define pir pair <ll, ll>
#define pb emplace_back
#define i128 __int128
using namespace std;
const ll maxn = 2e6 + 10, inf = 1e9;
ll n, a[maxn], b[maxn], id[maxn];
ll query() {
	printf("0");
	for(ll i = 1; i <= n; i++) printf(" %d", b[i]);
	puts(""), fflush(stdout);
	ll x; scanf("%d", &x); return x;
}
void solve(ll l, ll r, ll c) {
	if(l == r) { a[l] = c; return; }
	ll mid = l + r >> 1;
	ll e = c == 1? 2 : 1;
	for(ll i = 1; i <= n; i++)
		if(l <= i && i <= mid) b[i] = c;
		else b[i] = e;
	if(query()) solve(l, mid, c);
	else solve(mid + 1, r, c);
}
void work(ll p, ll q) {
	ll l = 1, r = n;
	ll lp, rp, lq, rq;
	ll e = min(p, q) > 1? 1 : (max(p, q) == 2? 3 : 2);
	while(l < r) {
		ll mid = l + r >> 1;
		for(ll i = 1; i <= n; i++)
			if(i > mid && i <= r) b[i] = q;
			else b[i] = p;
		ll tmp = query();
		if(tmp == 0) {
			lp = mid + 1, rp = r;
			lq = l, rq = mid; break;
		}
		if(tmp == 2) {
			lp = l, rp = mid;
			lq = mid + 1, rq = r; break;
		}
		for(ll i = mid + 1; i <= r; i++) b[i] = e;
		if(query()) r = mid;
		else l = mid + 1;
	}
	while(lp < rp && lq < rq) {
		ll midp = lp + rp >> 1, midq = lq + rq >> 1;
		for(ll i = 1; i <= n; i++)
			if(midp < i && i <= rp || lq <= i && i <= midq)
				b[i] = q;
			else b[i] = p;
		ll tmp = query();
		if(tmp == 0)
			lp = midp + 1, lq = midq + 1;
		else if(tmp == 2)
			rp = midp, rq = midq;
		else {
			for(ll i = lq; i <= midq; i++) b[i] = p;
			if(query()) rp = midp, lq = midq + 1;
			else lp = midp + 1, rq = midq;
		}
	}
	solve(lp, rp, p);
	solve(lq, rq, q);
}
int main() {
	scanf("%d", &n);
	for(ll i = 1; i <= n; i++) id[i] = i;
	random_shuffle(id + 1, id + 1 + n);
	for(ll i = 1; 2 * i <= n; i++)
		work(id[2 * i], id[2 * i - 1]);
	if(n & 1) {
		for(ll i = 1; i <= n; i++)
			if(!a[i]) a[i] = id[n];
	} printf("1 ");
	for(ll i = 1; i <= n; i++) printf("%d ", a[i]);
	return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 0
Wrong Answer
time: 1ms
memory: 7848kb

input:

5
2
1
1
1
1
2
2
2

output:

0 4 4 4 5 5
0 4 4 5 5 4
0 4 4 5 4 4
0 4 1 1 1 1
0 3 3 3 2 2
0 3 3 3 1 1
0 3 3 2 3 3
0 3 1 1 1 1
1 3 1 2 1 5 

result:

wrong answer Wrong Anser