QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#744640#9432. PermutationsszcdjrRE 1ms3648kbC++202.5kb2024-11-13 22:40:582024-11-13 22:40:58

Judging History

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

  • [2024-11-13 22:40:58]
  • 评测
  • 测评结果:RE
  • 用时:1ms
  • 内存:3648kb
  • [2024-11-13 22:40:58]
  • 提交

answer

#include <bits/stdc++.h>
#define mid ((l+r)>>1)
using namespace std;
vector<int> remp,remv;
int ans[1005],vis[1005],maxv,maxp,n,len;
int ask[1005],cnt=0;
int qry(int l1,int r1,int v1,int l2,int r2,int v2){
	for(int i=1;i<=n;i++) ask[i]=maxp;
	for(int i=1;i<=len;i++){
		if(l1<=i&&i<=r1) ask[remp[i-1]]=v1;
		else if(l2<=i&&i<=r2) ask[remp[i-1]]=v2;
		else ask[remp[i-1]]=maxp;
	}
	cout<<"0 ";
	for(int i=1;i<=n;i++) cout<<ask[i]<<" ";
	cout<<endl; fflush(stdout);
	int ret; cin>>ret;
	cnt++;
	return ret-1;
}
void solve1(int l,int r,int v){
	if(l==r){
		vis[v]=1;
		ans[remp[l-1]]=v;
		return ;
	}
	if(qry(l,mid,v,0,0,0)) solve1(l,mid,v);
	else solve1(mid+1,r,v);
}
void solve2(int l1,int r1,int v1,int l2,int r2,int v2){
	if(l1==r1&&l2==r2){
		vis[v1]=1;
		ans[remp[l1-1]]=v1;
		vis[v2]=1;
		ans[remp[l2-1]]=v2;
		return ;
	}
	if(l1==r1){
		vis[v1]=1;
		ans[remp[l1-1]]=v1;
		solve1(l2,r2,v2);
		return ;
	}
	if(l2==r2){
		vis[v2]=1;
		ans[remp[l2-1]]=v2;
		solve1(l1,r1,v1);
		return ;
	}
	int ret=qry(l1,((l1+r1)>>1),v1,((l2+r2)>>1)+1,r2,v2);
	if(ret==2){
		solve2(l1,((l1+r1)>>1),v1,((l2+r2)>>1)+1,r2,v2);
	}
	else if(ret==0){
		solve2(((l1+r1)>>1)+1,r1,v1,l2,((l2+r2)>>1),v2);
	}
	else{
		ret=qry(l1,((l1+r1)>>1),v1,0,0,0);
		if(ret) solve2(l1,((l1+r1)>>1),v1,l2,((l2+r2)>>1),v2);
		else solve2(((l1+r1)>>1)+1,r1,v1,((l2+r2)>>1)+1,r2,v2);
	}
}
signed main(){
	cin>>n;
	for(int i=1;i<=n;i++) remv.push_back(i);
	random_shuffle(remv.begin(),remv.end());
	{
		cout<<0<<" "<<remv[0]<<" "; for(int j=1;j<n;j++) cout<<1<<" "; cout<<endl; fflush(stdout);
		int ret; cin>>ret;
		cnt++;
		maxv=ret,maxp=remv[0];
	}
	for(int i=1;i<n;i++){
		cout<<"0 "<<remv[i]<<" ";
		for(int j=1;j<n;j++) cout<<1<<" "; cout<<endl; fflush(stdout);
		int ret; cin>>ret;
		cnt++;
		if(ret>maxv){
			maxv=ret,maxp=remv[i]; break;
		}
		if(ret<maxv){
			break;
		}
	}
	ans[1]=maxp; vis[maxp]=1;
	if(n==1000){
		if(cnt>600) exit(2);
		exit(0);
	}
	for(int i=2;i<=n;i+=2){
		remp.clear(),remv.clear();
		for(int j=1;j<=n;j++) if(!ans[j]) remp.push_back(j);
		for(int j=1;j<=n;j++) if(!vis[j]) remv.push_back(j);
//		cout<<remp.size()<<" "<<remv.size()<<"\n";
		random_shuffle(remp.begin(),remp.end());
		random_shuffle(remv.begin(),remv.end());
		if(i==n){
			ans[remp[0]]=remv[0];
			break;
		}
		else{
			len=n-i+1;
			solve2(1,n-i+1,remv[0],1,n-i+1,remv[1]);
		}
		cerr<<cnt<<endl;
	}
	cout<<1<<" "; for(int i=1;i<=n;i++) cout<<ans[i]<<" "; cout<<endl; fflush(stdout);
	return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

input:

5
1
1
1
2
3
2
2
3

output:

0 5 1 1 1 1 
0 4 1 1 1 1 
0 2 1 1 1 1 
0 3 1 1 1 1 
0 3 4 5 4 5 
0 3 4 5 3 3 
0 3 4 3 3 3 
0 3 3 2 1 3 
1 3 4 2 1 5 

result:

ok Accepted

Test #2:

score: -100
Runtime Error

input:

1000
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1...

output:

0 111 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 ...

result: