QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#646003#6303. InversionioritWA 66ms67844kbC++142.9kb2024-10-16 20:50:422024-10-16 20:50:44

Judging History

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

  • [2024-10-16 20:50:44]
  • 评测
  • 测评结果:WA
  • 用时:66ms
  • 内存:67844kb
  • [2024-10-16 20:50:42]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;
#define ll long long
namespace IO {
//	#if ONLINE_JUDGE
//	#define getc() (IS == IT && (IT = (IS = ibuf) + fread(ibuf, 1, IL, stdin), IS == IT) ? EOF : *IS++)
//	#else
	#define getc() getchar()
//	#endif
	const int IL = 1 << 21, OL = 1 << 21;
	int olen = 0;
	char ibuf[IL], *IS = ibuf, *IT = ibuf, obuf[OL];
	inline int read() {
		int x;
		cin >> x;
		return x;
	}
	inline double readdb() {
		register char ch = getc(); register double x = 0, f = 1;
		while(!isdigit(ch)) { if(ch == '-') f = -1; ch = getc(); }
		while(isdigit(ch)) x = x * 10 + ch - 48, ch = getc();
		if(ch == '.') {
			register double b = 0.1;
			ch = getc();
			while(isdigit(ch)) x += (ch - 48) * b, b *= 0.1, ch = getc();
		}
		return x * f;
	}
	inline int readstr(char *s) {
		register char ch = getc(); register int len = 0;
		while(!isalpha(ch)) ch = getc();
		while(isalpha(ch)) s[++len] = ch, ch = getc();
		return len;
	}
	inline void flush() { fwrite(obuf, 1, olen, stdout); olen = 0; }
	inline void putc(register char ch) { obuf[olen++] = ch; }
	template<class T>
	inline void write(register T x) {
		if(x < 0) obuf[olen++] = '-', x = -x;
		if(x > 9) write(x / 10);
		obuf[olen++] = x % 10 + 48;
	}
} using namespace IO;
const int N = 4e3 + 10;
int cnt = 0;
int ans[N][N];
bool cmp(int x, int y) {
//	return 0;
	if(x > y) swap(x, y);
	if(x == y - 1) {
		cnt++;
//		return 0;
		if(~ans[x][y]) return ans[x][y];
		printf("? %d %d\n", x, y);
		cout << endl; 
		fflush(stdout);
		return ans[x][y] = read();
	}
//	cnt+=4;
//	return 0;
	int res = 0;
	if(!~ans[x][y]) {
		printf("? %d %d\n", x, y);
		cout << endl; 
		fflush(stdout);
		ans[x][y] = read();
	}
	res ^= ans[x][y];
	if(!~ans[x+1][y]) {
		printf("? %d %d\n", x+1, y);
		cout << endl; 
		fflush(stdout);
		ans[x+1][y] = read();
	}
	res ^= ans[x+1][y];
	if(!~ans[x][y-1]) {
		printf("? %d %d\n", x, y-1);
		cout << endl; 
		fflush(stdout);
		ans[x][y-1] = read();
	}
	res ^= ans[x][y-1];
	
	if(!~ans[x+1][y-1]) {
		if(x==y-2) ans[x+1][y-1] = 0;
		else {printf("? %d %d\n", x+1, y-1);
		cout << endl; 
		fflush(stdout);
		ans[x+1][y-1] = read();
			
		}
	}
	res ^= ans[x+1][y-1];
	return res;
}
int p[N], tmp[N];
void solve(int l, int r) {
	if(l == r) return;
//	if(l==1) {
//		puts("q");
//	}
	int mid = l + r >> 1;
	solve(l, mid);
	solve(mid + 1, r);
	int i = l, j = mid + 1, k = i;
	while(i <= mid && j <= r) {
		if(cmp(p[i], p[j])) tmp[k++] = p[j++];
		else tmp[k++] = p[i++];
	}
	while(i <= mid) tmp[k++] = p[i++];
	while(j <= r) tmp[k++] = p[j++];
	for(i = l; i <= r; i++) p[i] = tmp[i];
}
int id[N];
int main() {
	int n;
	memset(ans,-1,sizeof(ans));
	n = read();
	iota(p + 1, p + 1 + n, 1);
	solve(1, n);
	for(int i = 1; i <= n; i++)
		id[p[i]] = i;
	printf("! ");
	for(int i = 1; i <= n; i++)
		printf("%d ", id[i]);
	fflush(stdout);
//	cout << cnt << endl;
	return 0;
}

详细

Test #1:

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

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: 66ms
memory: 67844kb

input:

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

output:

? 1 2

? 3 4

? 1 3

? 2 3

? 5 6

? 7 8

? 5 7

? 6 7

? 5 8

? 6 8

? 1 7

? 2 7

? 1 6

? 2 6

? 1 5

? 2 5

? 1 4

? 2 4

? 1 8

? 2 8

? 3 8

? 3 7

? 4 8

? 4 7

? 9 10

? 11 12

? 10 11

? 9 11

? 9 12

? 10 12

? 13 14

? 15 16

? 14 15

? 13 15

? 13 16

? 14 16

? 10 14

? 11 14

? 10 13

...

result:

wrong output format Unexpected end of file - int32 expected