QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#294604#6303. Inversionxzf_200906WA 62ms19336kbC++14937b2023-12-30 14:55:192023-12-30 14:55:20

Judging History

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

  • [2023-12-30 14:55:20]
  • 评测
  • 测评结果:WA
  • 用时:62ms
  • 内存:19336kb
  • [2023-12-30 14:55:19]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;
int num[2005][2005],a[2005],p[2005];
int queryInv(int a,int b){
	if(a>=b) return 0;
	if(num[a][b]==-1){
		cout<<"? "<<a<<' '<<b<<endl;
		cin>>num[a][b];
	}
	return num[a][b];
}
int compare(int a,int b){
	if(queryInv(a,b)^queryInv(a,b-1)^queryInv(a+1,b)^queryInv(a+1,b-1)) return 1;
	return 0;
}
signed main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	int n;
	cin>>n;
	a[1]=1;
	p[1]=1;
	memset(num,-1,sizeof(num));
	for(int i=2;i<=n;i++){
		int l=1,r=i-1;
		while(l<=r){
			int mid=(l+r)>>1;
			if(compare(p[mid],i)) r=mid-1;
			else l=mid+1;
		}
		int pos=r+1;
		a[i]=pos;
		for(int j=1;j<i;j++){
			if(a[j]>=pos) a[j]++;
		}
		for(int j=i;j>pos;j--) p[j]=p[j-1];
		p[pos]=i;
		int nm=0;
		for(int j=i-1;j>=1;j--){
			if(a[i]<a[j]) nm^=1;
			num[j][i]=nm;
		}
	}
	cout<<"! ";
	for(int i=1;i<=n;i++) cout<<a[i]<<' ';
	return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

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: 62ms
memory: 19336kb

input:

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

output:

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

result:

wrong answer Wa.