QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#180019#1464. Interactive AlgorithmFISHER_WA 2ms3616kbC++142.2kb2023-09-15 14:38:522023-09-15 14:38:54

Judging History

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

  • [2023-09-15 14:38:54]
  • 评测
  • 测评结果:WA
  • 用时:2ms
  • 内存:3616kb
  • [2023-09-15 14:38:52]
  • 提交

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 - 1; i++) {
		int r = i + 1, mx = queryd(n, i);
		for (int t = 1; t <= mx; t++) {
			for (int j = 8; ~j; j--)
				if (int nr = r + (1 << j); nr <= n && queryd(nr, i) < t) r = nr;
			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: 2ms
memory: 3616kb

input:

5
1
1
1
1
3
2
2
1
1
2
2
2
1
1
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 
! 5 1 7 1 5 

result:

wrong output format Unexpected end of file - int32 expected