QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#477773#6303. InversionpavementTL 4ms19396kbC++171.2kb2024-07-14 10:26:112024-07-14 10:26:12

Judging History

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

  • [2024-07-14 10:26:12]
  • 评测
  • 测评结果:TL
  • 用时:4ms
  • 内存:19396kb
  • [2024-07-14 10:26:11]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;

int n, a[2005], chc[2005][2005];

int qry(int l, int r) {
	if (l >= r) {
		return 0;
	}
	if (a[r]) {
		bool ret = 0;
		for (int x = l; x <= r; x++) {
			for (int y = x + 1; y <= r; y++) {
				if (a[x] > a[y]) {
					ret ^= 1;
				}
			}
		}
		return ret;
	}
	if (chc[l][r] != -1) {
		return chc[l][r];
	}
	bool ret;
	cout << "? " << l << ' ' << r << endl;
	cin >> ret;
	return chc[l][r] = ret;
}

int main() {
	memset(chc, -1, sizeof chc);
	a[1] = 1;
	cin >> n;
	for (int i = 2; i <= n; i++) {
		int lo = 1, hi = i - 1, val = i;
		while (lo <= hi) {
			int mid = (lo + hi) / 2, pos = -1;
			for (int j = 1; j < i; j++) {
				if (a[j] == mid) {
					pos = j;
					break;
				}
			}
			assert(pos != -1);
			// [pos, i]
			int x = qry(pos + 1, i);
			int y = qry(pos, i);
			bool cur = y ^ x ^ qry(pos, i - 1) ^ qry(pos + 1, i - 1);
			if (cur) {
				// mid > a[i]
				val = mid;
				hi = mid - 1;
			} else {
				lo = mid + 1;
			}
		}
		for (int j = 1; j < i; j++) {
			if (a[j] >= val) {
				a[j]++;
			}
		}
		a[i] = val;
	}
	cout << "! ";
	for (int i = 1; i <= n; i++) {
		cout << a[i] << ' ';
	}
	cout << endl;
}

详细

Test #1:

score: 100
Accepted
time: 4ms
memory: 19396kb

input:

3
0
1
0

output:

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

result:

ok OK, guesses=3

Test #2:

score: -100
Time Limit Exceeded

input:

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

output:

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

result: