QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#744660#9432. PermutationsszcdjrRE 318ms3868kbC++202.5kb2024-11-13 22:44:422024-11-13 22:44:43

Judging History

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

  • [2024-11-13 22:44:43]
  • 评测
  • 测评结果:RE
  • 用时:318ms
  • 内存:3868kb
  • [2024-11-13 22:44:42]
  • 提交

answer

#include <bits/stdc++.h>
#define mid ((l+r)>>1)
using namespace std;
mt19937 rng(time(0));
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);
	shuffle(remv.begin(),remv.end(),rng);
	{
		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;
	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";
		shuffle(remp.begin(),remp.end(),rng);
		shuffle(remv.begin(),remv.end(),rng);
		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]);
		}
		if(cnt>6600){
			if(i>=500) exit(2);
			else exit(0);
		}
	}
	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: 3716kb

input:

5
1
2
1
1
1

output:

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

result:

ok Accepted

Test #2:

score: 0
Accepted
time: 318ms
memory: 3780kb

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
2
2
2
2
2
3
3
1
1
2
2
2
2
1
3
3
2
1
2
1
1
3
3
2
2
1
1
2
2
1
2
1
2
1
3
2
1
2
2
2
2
3
3
2
1
2
1
2
2
2
1
2
1
2
1
2
2
2
1
2
1
2
2
1
3
3
2
1
1
1...

output:

0 543 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:

ok Accepted

Test #3:

score: 0
Accepted
time: 1ms
memory: 3660kb

input:

1
1

output:

0 1 
1 1 

result:

ok Accepted

Test #4:

score: 0
Accepted
time: 1ms
memory: 3684kb

input:

2
2
1

output:

0 2 1 
0 1 1 
1 2 1 

result:

ok Accepted

Test #5:

score: 0
Accepted
time: 1ms
memory: 3868kb

input:

3
2
1
3

output:

0 3 1 1 
0 1 1 1 
0 3 1 2 
1 3 1 2 

result:

ok Accepted

Test #6:

score: 0
Accepted
time: 0ms
memory: 3692kb

input:

4
1
2
1
2

output:

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

result:

ok Accepted

Test #7:

score: 0
Accepted
time: 1ms
memory: 3776kb

input:

6
1
2
3
2
2
2
1
1

output:

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

result:

ok Accepted

Test #8:

score: 0
Accepted
time: 0ms
memory: 3668kb

input:

7
2
1
2
2
2
2
3
2
2
1
3

output:

0 3 1 1 1 1 1 1 
0 1 1 1 1 1 1 1 
0 3 5 2 2 5 2 5 
0 3 3 2 2 3 2 3 
0 3 3 2 5 3 2 3 
0 3 3 2 3 3 2 3 
0 3 3 2 3 3 5 3 
0 3 1 3 4 1 3 4 
0 3 3 3 4 3 3 4 
0 3 3 3 4 3 3 1 
0 3 7 3 3 6 3 3 
1 3 7 2 1 6 5 4 

result:

ok Accepted

Test #9:

score: 0
Accepted
time: 0ms
memory: 3724kb

input:

8
1
2
1
2
1
1
3
1
1
2

output:

0 7 1 1 1 1 1 1 1 
0 3 1 1 1 1 1 1 1 
0 3 8 1 8 8 1 1 1 
0 3 1 8 3 1 3 3 8 
0 3 1 3 3 1 3 3 3 
0 3 3 8 3 3 3 3 3 
0 3 4 2 3 2 2 4 3 
0 3 4 3 3 2 2 3 3 
0 3 6 3 3 5 6 3 3 
0 3 3 3 3 3 5 3 3 
1 3 7 2 1 6 5 4 8 

result:

ok Accepted

Test #10:

score: 0
Accepted
time: 1ms
memory: 3772kb

input:

9
1
1
1
1
1
1
1
2
2
1
3
3
2
1
2
2
3
1
3
1

output:

0 8 1 1 1 1 1 1 1 1 
0 1 1 1 1 1 1 1 1 1 
0 9 1 1 1 1 1 1 1 1 
0 6 1 1 1 1 1 1 1 1 
0 4 1 1 1 1 1 1 1 1 
0 7 1 1 1 1 1 1 1 1 
0 2 1 1 1 1 1 1 1 1 
0 3 1 1 1 1 1 1 1 1 
0 3 9 8 9 8 9 9 8 8 
0 3 9 3 9 3 9 9 3 3 
0 3 3 8 3 9 3 3 8 9 
0 3 3 3 3 9 3 3 8 3 
0 3 7 5 5 3 7 7 3 5 
0 3 3 5 5 3 3 3 3 5 
0 3 5 ...

result:

ok Accepted

Test #11:

score: 0
Accepted
time: 1ms
memory: 3660kb

input:

10
1
2
2
1
3
2
2
1
2
1
1
1
3
3
2

output:

0 10 1 1 1 1 1 1 1 1 1 
0 3 1 1 1 1 1 1 1 1 1 
0 3 10 10 7 7 7 7 10 7 10 
0 3 3 3 7 7 7 7 3 7 3 
0 3 7 10 3 3 3 3 7 3 10 
0 3 7 3 3 3 3 3 3 3 10 
0 3 7 3 3 3 3 3 3 3 3 
0 3 3 3 5 6 6 5 6 5 6 
0 3 3 3 6 3 5 6 3 3 5 
0 3 3 3 6 3 3 6 3 3 3 
0 3 3 3 3 3 3 3 3 3 5 
0 3 3 3 4 4 3 1 1 3 1 
0 3 3 3 1 3 3 4 ...

result:

ok Accepted

Test #12:

score: 0
Accepted
time: 0ms
memory: 3704kb

input:

11
1
1
1
1
1
1
1
1
1
2
3
2
2
2
1
2
2
1
2
2
1
3
1
1
2
1
3

output:

0 8 1 1 1 1 1 1 1 1 1 1 
0 1 1 1 1 1 1 1 1 1 1 1 
0 9 1 1 1 1 1 1 1 1 1 1 
0 6 1 1 1 1 1 1 1 1 1 1 
0 4 1 1 1 1 1 1 1 1 1 1 
0 7 1 1 1 1 1 1 1 1 1 1 
0 2 1 1 1 1 1 1 1 1 1 1 
0 10 1 1 1 1 1 1 1 1 1 1 
0 11 1 1 1 1 1 1 1 1 1 1 
0 3 1 1 1 1 1 1 1 1 1 1 
0 3 11 10 11 11 10 10 11 10 10 11 
0 3 11 10 3 3...

result:

ok Accepted

Test #13:

score: 0
Accepted
time: 0ms
memory: 3708kb

input:

12
1
2
2
2
1
1
2
2
1
1
2
2
3
3
1
1
1
1
1
1

output:

0 10 1 1 1 1 1 1 1 1 1 1 1 
0 3 1 1 1 1 1 1 1 1 1 1 1 
0 3 10 10 10 10 1 10 1 10 1 1 1 
0 3 10 10 10 10 3 10 3 10 3 3 3 
0 3 1 1 10 1 3 10 3 10 3 3 3 
0 3 10 3 3 10 3 1 3 3 3 3 3 
0 3 3 3 1 3 3 3 3 3 3 3 3 
0 3 5 3 3 5 2 5 5 5 2 2 2 
0 3 5 3 3 5 3 5 5 5 3 3 3 
0 3 3 3 3 3 2 3 3 3 5 2 5 
0 3 3 3 3 3 ...

result:

ok Accepted

Test #14:

score: 0
Accepted
time: 0ms
memory: 3800kb

input:

13
1
1
2
3
2
2
3
1
2
1
3
3
2
3
2
1
2
2
2
1
1
1
2
2
3
1

output:

0 8 1 1 1 1 1 1 1 1 1 1 1 1 
0 1 1 1 1 1 1 1 1 1 1 1 1 1 
0 13 1 1 1 1 1 1 1 1 1 1 1 1 
0 13 3 6 6 3 6 6 3 6 3 3 6 3 
0 13 13 6 13 3 13 6 3 13 13 3 6 13 
0 13 13 6 13 13 13 6 13 13 13 13 6 13 
0 13 13 6 13 13 13 13 13 13 13 13 6 3 
0 13 13 6 13 13 13 13 13 13 13 13 13 13 
0 13 12 8 8 12 8 8 8 12 12 ...

result:

ok Accepted

Test #15:

score: 0
Accepted
time: 0ms
memory: 3772kb

input:

14
2
1
2
1
1
3
2
3
1
1
2
2
2
2
1
3
2
2
1
3
2
2
2
2
3
1
1

output:

0 13 1 1 1 1 1 1 1 1 1 1 1 1 1 
0 3 1 1 1 1 1 1 1 1 1 1 1 1 1 
0 13 5 5 5 2 5 2 2 5 2 5 5 2 2 
0 13 5 5 5 13 5 13 13 5 13 5 5 13 13 
0 13 13 13 13 2 13 5 5 13 5 13 13 2 2 
0 13 13 13 13 5 13 13 13 13 2 13 13 13 5 
0 13 13 13 13 13 13 13 13 13 13 13 13 13 5 
0 13 3 9 3 9 3 9 3 9 13 9 3 3 13 
0 13 13 ...

result:

ok Accepted

Test #16:

score: 0
Accepted
time: 1ms
memory: 3724kb

input:

15
1
1
2
3
2
2
2
2
3
2
2
3
1
2
1
3
3
2
2
1
1
2
2
1
3
1
3
2
2
1

output:

0 15 1 1 1 1 1 1 1 1 1 1 1 1 1 1 
0 14 1 1 1 1 1 1 1 1 1 1 1 1 1 1 
0 13 1 1 1 1 1 1 1 1 1 1 1 1 1 1 
0 13 4 15 15 4 15 4 4 4 4 4 15 15 15 15 
0 13 13 15 15 13 13 4 13 4 4 4 13 13 13 15 
0 13 13 13 13 13 13 4 13 4 4 4 13 13 13 13 
0 13 13 13 13 13 13 4 13 13 4 13 15 15 13 13 
0 13 13 13 13 13 13 4 1...

result:

ok Accepted

Test #17:

score: -100
Runtime Error

input:

975
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 791 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: