QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#740932#6303. InversionOIer_kzc#WA 61ms7872kbC++171.2kb2024-11-13 12:30:132024-11-13 12:30:19

Judging History

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

  • [2024-11-13 12:30:19]
  • 评测
  • 测评结果:WA
  • 用时:61ms
  • 内存:7872kb
  • [2024-11-13 12:30:13]
  • 提交

answer

#include <stdio.h>
#include <string.h>

#include <random>
#include <chrono>
#include <algorithm>

#define LOG(FMT...) fprintf(stderr, FMT)

using namespace std;

typedef long long LL;
constexpr int N = 2005;

mt19937 rnd(chrono::steady_clock::now().time_since_epoch().count());

int n;
int a[N], b[N];
int cur;
bool f[N][N];

bool Q(int x) {
	int s, t;
	printf("? %d %d\n", x, cur);
	fflush(stdout);
	scanf("%d", &s);
	if (x == cur - 1) {
		return s;
	}
	printf("? %d %d\n", x + 1, cur);
	fflush(stdout);
	scanf("%d", &t);
	s ^= t;
	return s ^ f[x][cur - 1] ^ f[x + 1][cur - 1];
}

int main() {
	scanf("%d", &n);
	b[1] = 1;
	for (cur = 2; cur <= n; ++cur) {
		int l = 1, r = cur, md;
		while (l < r) {
			int md = l + r >> 1;
			if (Q(b[md])) {
				r = md;
			} else {
				l = md + 1;
			}
		}
		for (int j = cur; j > r; --j) {
			b[j] = b[j - 1];
		}
		b[r] = cur;
		for (int i = 1; i <= cur; ++i) {
			a[b[i]] = i;
		}
		f[cur - 1][cur] = (a[cur - 1] > cur);
		for (int x = cur - 2; x; --x) {
			f[x][cur] = (a[x] > a[cur]) ^ f[x + 1][cur] ^ f[x][cur - 1] ^ f[x + 1][cur - 1];
		}
	}
	printf("!");
	for (int i = 1; i <= n; ++i) {
		printf(" %d", a[i]);
	}
	puts("");
	fflush(stdout);
	return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 0ms
memory: 3948kb

input:

3
0
1
0
1

output:

? 1 2
? 2 3
? 1 3
? 2 3
! 2 3 1

result:

ok OK, guesses=4

Test #2:

score: -100
Wrong Answer
time: 61ms
memory: 7872kb

input:

1993
0
0
0
0
0
0
1
1
0
0
1
0
0
0
0
0
1
0
1
0
1
0
1
0
0
1
0
1
1
0
1
1
0
0
0
1
1
1
1
1
1
1
0
0
0
0
0
0
0
0
0
0
0
0
0
1
0
0
1
0
1
1
0
1
1
0
1
0
1
1
1
1
1
1
0
1
0
1
1
0
1
1
0
1
0
0
0
0
0
1
0
0
1
0
1
0
0
1
1
0
1
1
0
0
1
1
1
1
1
1
1
1
0
1
0
0
0
0
0
0
0
1
0
0
1
0
1
1
1
0
0
0
1
1
0
0
0
0
0
0
1
1
0
0
1
1
0
0...

output:

? 1 2
? 2 3
? 2 4
? 3 4
? 3 4
? 3 5
? 4 5
? 2 5
? 3 5
? 1 5
? 2 5
? 2 6
? 3 6
? 1 6
? 2 6
? 5 6
? 2 7
? 3 7
? 6 7
? 5 7
? 6 7
? 1 8
? 2 8
? 3 8
? 4 8
? 2 8
? 3 8
? 2 9
? 3 9
? 6 9
? 7 9
? 5 9
? 6 9
? 1 10
? 2 10
? 3 10
? 4 10
? 8 10
? 9 10
? 2 11
? 3 11
? 3 11
? 4 11
? 10 11
? 2 12
? 3 12
? 11 12
? ...

result:

wrong answer Wa.