QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#279804#6303. Inversionforget-star#WA 70ms19344kbC++141.0kb2023-12-09 09:43:462023-12-09 09:43:47

Judging History

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

  • [2023-12-09 09:43:47]
  • 评测
  • 测评结果:WA
  • 用时:70ms
  • 内存:19344kb
  • [2023-12-09 09:43:46]
  • 提交

answer

#include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<ctime>
#include<vector>
using namespace std;
typedef long long ll;
const int N=2005;
int a[N],b[N],f[N][N],n;
int query(int x,int y)
{
	if(x>=y) return 0;
	if(f[x][y]!=-1) return f[x][y];
	cout<<"? "<<x<<" "<<y<<'\n';
	fflush(stdout);
	int tmp;cin>>tmp;
	return f[x][y]=tmp;
}
int check(int x,int y)
{
	return query(x,y)^query(x+1,y)^query(x,y-1)^query(x+1,y-1);
}
int main()
{
	cin>>n;memset(f,-1,sizeof(f));
	for(int i=1;i<=n;i++) f[i][i]=0;
	for(int i=1;i<=n;i++) a[i]=i;
	for(int i=2;i<=n;i++)
	{
		int l=1,r=i-1,res=i;
		while(l<=r)
		{
			int mid=(l+r)>>1;
			if(check(a[mid],i)) res=mid,r=mid-1;
			else l=mid+1;
		}
		for(int j=i;j>res;j--) a[j]=a[j-1];
		a[res]=i;
		for(int j=1;j<=i;j++) b[a[j]]=j;
		for(int j=i-1;j>=1;j--) res^=(b[j]>b[i]),f[j][i]=res^f[j][i-1];
	}
	cout<<"! ";
	for(int i=1;i<=n;i++) b[a[i]]=i;
	for(int i=1;i<=n;i++) cout<<b[i]<<" ";
	fflush(stdout);
	return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

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: 70ms
memory: 19340kb

input:

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

output:

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

result:

wrong answer Wa.