QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#360530#6303. InversionSiilhouetteWA 40ms19692kbC++141.7kb2024-03-21 21:05:572024-03-21 21:05:58

Judging History

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

  • [2024-03-21 21:05:58]
  • 评测
  • 测评结果:WA
  • 用时:40ms
  • 内存:19692kb
  • [2024-03-21 21:05:57]
  • 提交

answer

#define _CRT_SECURE_NO_WARNINGS
#include<queue>
#include<cmath>
#include<string>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;

const int N=2010;
int n,tot,cnt,tim,v[N],ans[N][N],a[N],c[N];

//struct Node{int l,r;}a[N];

inline bool ask(int l,int r)
{
	if(l==r)return 0;
	int res;
	printf("? %d %d\n",l,r);
	cout.flush();
	scanf("%d",&res);
	return ans[l][r]=res;
}

inline bool query(int l,int r)
{
	//cout<<"query "<<l<<" "<<r<<endl;
	//cout<<"ans "<<ans[l][r]<<endl;
	if(l==r)return 0;
	if(l+1==r)return (~ans[l][r])?ans[l][r]:ask(l,r);
	int x=(~ans[l][r])?ans[l][r]:ask(l,r);
	int y=(~ans[l+1][r])?ans[l+1][r]:ask(l+1,r);
	int z=(~ans[l][r-1])?ans[l][r-1]:ask(l,r-1);
	int w=(~ans[l+1][r-1])?ans[l+1][r-1]:ask(l+1,r-1);
	return x^y^z^w;
}


inline void insert(int x,int d)
{
	for(int i=cnt;i>=d;i--)
		a[i+1]=a[i];
	a[d]=x;
	cnt++;tim++;
	for(int i=d+1;i<=cnt;i++)
		v[a[i]]=tim;
	for(int i=x-1,pos=0;i;i--)
	{
		if(v[i]==tim)pos^=1;
		ans[i][x]=ans[i][x-1]^pos;
	}
}

int main()
{
	int pos;
	memset(ans,-1,sizeof(ans));
	scanf("%d",&n);
	for(int i=1;i<=n;i++)ans[i][i]=0;
	pos=ask(1,2);
	insert(1,1);
	insert(2,pos?1:2);
	for(int i=3;i<=n;i++)
	{
		/**/
		if(query(a[1],i)){ 
			//cout<<"!"<<endl;
			insert(i,1);continue; }
		if(!query(a[cnt],i)){ 
			//cout<<"#"<<endl;
			insert(i,cnt+1);continue; }
			
		int l=1,r=cnt;
		while(l<r)
		{
			int mid=l+r>>1;
			if(query(a[mid],i))r=mid;
			else l=mid+1;
		}
		//if(l==cnt)insert(i,query(a[cnt],i)?cnt:cnt+1);
		insert(i,l);
	}
	for(int i=1;i<=n;i++)
		c[a[i]]=i;
	putchar('!');
	for(int i=1;i<=n;i++)
		printf(" %d",c[i]);
	putchar('\n');
	return 0;
}

詳細信息

Test #1:

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

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: 40ms
memory: 19692kb

input:

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

output:

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

result:

wrong output format Unexpected end of file - int32 expected