QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#286701#6303. Inversion000226#WA 76ms19260kbC++171.9kb2023-12-18 13:37:382023-12-18 13:37:38

Judging History

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

  • [2023-12-18 13:37:38]
  • 评测
  • 测评结果:WA
  • 用时:76ms
  • 内存:19260kb
  • [2023-12-18 13:37:38]
  • 提交

answer

#include <bits/stdc++.h>

#define lep(i, l, r) for(int i = (l); i <= (r); i ++)
#define rep(i, l, r) for(int i = (l); i >= (r); i --)
#define debug(...) fprintf (stderr, __VA_ARGS__)

using std :: cin;
using std :: cout;
using std :: endl;
using std :: cerr;
using i64 = long long;

const int P = 998244353;
inline int mod(int x) { return x + (x >> 31 & P); }
inline void sub(int &x, int y) { x = mod(x - y); }
inline void pls(int &x, int y) { x = mod(x + y - P); }
inline int add(int x, int y) { return mod(x + y - P); }
inline int dec(int x, int y) { return mod(x - y); }
inline int power(int x, int k) {
	int res = 1; if (k < 0) k += P - 1;
	while (k) { if (k & 1) res = 1ll * res * x % P; x = 1ll * x * x % P; k >>= 1; }
	return res;
}

int qry (int l, int r) {
	if (l == r) return 0;
	if (l > r) return 0;
	cout << "? " << l << ' ' << r << endl;
	int o;
	cin >> o;
	return o;
}

const int N = 2000 + 5;

int n;
int ans[N], dans[N];
int f[N][N];

inline int query (int l, int r) { // l > r
	int o = 0;
	if (l > r) std :: swap (l, r), o ^= 1;
	if (f[l][r] == -1) f[l][r] = qry (l, r);
	if (f[l + 1][r] == -1) f[l + 1][r] = qry (l + 1, r);
	if (f[l][r - 1] == -1) f[l][r - 1] = qry (l, r - 1);
	if (f[l + 1][r - 1] == -1) f[l + 1][r - 1] = qry (l + 1, r - 1);
	return f[l][r] ^ f[l + 1][r] ^ f[l][r - 1] ^ f[l + 1][r - 1] ^ o;
}

int main() {
	std :: ios :: sync_with_stdio(false);
	srand (time(0));
	cin >> n;
	lep (i, 1, n) lep (j, 1, n) f[i][j] = -1;
	ans[1] = 1;
	for (int i = 2; i <= n; i ++) {
		int l = 1, r = i - 1, res = 0;
		while (l <= r) {
			int mid = (l + r) >> 1;
			if (query (ans[mid], i)) r = mid - 1;
			else res = mid, l = mid + 1;
		}
		rep (j, i, res + 2) ans[j] = ans[j - 1];
		ans[res + 1] = i;
	}
	lep (i, 1, n) dans[ans[i]] = i;
	cout << "! ";
	for (int i = 1; i <= n; i ++) cout << dans[i] << ' '; cout << endl;
	return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 1ms
memory: 3652kb

input:

3
0
0
1

output:

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

result:

ok OK, guesses=3

Test #2:

score: -100
Wrong Answer
time: 76ms
memory: 19260kb

input:

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

output:

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

result:

wrong output format Unexpected end of file - int32 expected