QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#751682#6303. InversionchenyitaooooWA 55ms17692kbC++23834b2024-11-15 20:07:542024-11-15 20:07:54

Judging History

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

  • [2024-11-15 20:07:54]
  • 评测
  • 测评结果:WA
  • 用时:55ms
  • 内存:17692kb
  • [2024-11-15 20:07:54]
  • 提交

answer

#include<bits/stdc++.h>
#define Ri register int  
using namespace std;
const int N=2005;
int a[N],F[N][N],b[N],n;
void ff(){
	fflush(stdout);
}
int qy(int l,int r){
	int x,y;
	printf("? %d %d\n",l,r);
	ff();
	scanf("%d",&x);
	if(l==r-1) return x;
	printf("? %d %d\n",l+1,r);
	ff();
	scanf("%d",&y);
	return x^y;
}
int main(){
	scanf("%d",&n);
	a[1]=1;
	for(Ri i=2; i<=n; ++i){
		for(Ri j=1; j<i; ++j){
			b[a[j]]=j;
		}
		int l=1,r=i-1,an=i;
		while(l<=r){
			int mid=(l+r)>>1;
			if(qy(b[mid],i)==1) r=mid-1,an=mid;
			else l=mid+1;
		}
//		printf(":%d %d:\n",i,an);
		for(Ri j=1; j<i; ++j){
			if(a[j]>=an) a[j]++;
		}
		a[i]=an;
		for(Ri j=i-1; j>=1; --j){
			F[j][i]=F[j+1][i]^F[j][i-1]^F[j+1][i-1]^(a[j]>a[i]);
		}
	}
	printf("! ");
	for(Ri i=1; i<=n; ++i) printf("%d ",a[i]);
	ff();
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

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: 55ms
memory: 17692kb

input:

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

output:

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

result:

wrong answer Wa.