QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#253618#6303. InversionSATSKYWA 54ms6140kbC++201.7kb2023-11-17 10:14:322023-11-17 10:14:32

Judging History

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

  • [2023-11-17 10:14:32]
  • 评测
  • 测评结果:WA
  • 用时:54ms
  • 内存:6140kb
  • [2023-11-17 10:14:32]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;using ll=long long;const ll inf=3e18;const int M=1e9+7;
int o,o2,tc;
vector<int>res;
struct S
{
	vector<int>arr,r2,rev;int n;
	map<pair<int,int>,int>mp;
	void ins(int id,int pos,int siz)
	{
		//cout<<siz<<':'<<pos<<'\n';
		int pt=0;r2[pos]=id;
		for(int i=1;i<=siz;i++)if(i!=pos)r2[i]=arr[++pt];
		swap(arr,r2);
	}
	int query(int l,int r)
	{
		if(l>r)return 0;
		if(mp.count({l,r}))return mp[{l,r}];
		cout<<"? "<<l<<" "<<r<<endl;
		int x=0;
		cin>>x;
		mp[{l,r}]=x;
		//for(int i=l;i<r;i++)for(int j=i+1;j<=r;j++)x^=(res[i]>res[j]);
		//cout<<l<<"#"<<r<<"#"<<x<<'\n';
		return x;
	}
	bool chk(int a,int b)//a<b 0:r[a]<r[b] 1:r[a]>r[b]
	{
		bool sw=0;if(a>b)swap(a,b),sw=1;
		bool x=query(a,b)^query(a+1,b)^query(a,b-1)^query(a+1,b-1);
		//cout<<a<<"!!"<<b<<"!!"<<x<<'\n';
		//if(bool(x)^(res[a]>res[b]))
		//{
		//	cout<<a<<"!!"<<b<<"!!"<<x<<'\n';
		//}
		return x^sw;
	}
	void solve()
	{
		cin>>n;arr.resize(n+1),r2.resize(n+1);
		
		//
		//res.resize(n+1);for(int i=1;i<=n;i++)cin>>res[i];
		//
		arr[1]=1;
		for(int i=2;i<=n;i++)
		{
			int p=i;
			if(chk(arr[1],p)){ins(p,1,i);continue;}
			if(!chk(arr[i-1],p)){ins(p,i,i);continue;}
			int l=1,r=i;while(l<r-1)
			{
				int mid=(l+r)/2;chk(arr[mid],p)?r=mid:l=mid;
			}
			ins(p,r,i);
		}
		rev.resize(n+1);for(int i=1;i<=n;i++)rev[arr[i]]=i;
		cout<<"!";for(int i=1;i<=n;i++)cout<<' '<<rev[i];cout<<endl;
	}
};
int main()
{
	//freopen("3.in","r",stdin);
	//cout<<fixed<<setprecision(12);
	//ios::sync_with_stdio(0);cin.tie(0);
	int t=1;//cin>>t;o=(t>50);
	//clock_t a=clock();
	while(t--){S SS;SS.solve();}
	//cout<<"Time:"<<double(clock()-a)<<'\n';
}

詳細信息

Test #1:

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

input:

3
0
0
0
0
1

output:

? 1 2
? 2 2
? 1 1
? 1 3
? 2 3
! 2 3 1

result:

ok OK, guesses=5

Test #2:

score: -100
Wrong Answer
time: 54ms
memory: 6140kb

input:

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

output:

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

result:

wrong output format Unexpected end of file - int32 expected