QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#741481#9432. PermutationhotdogsellerTL 1ms3776kbC++141.9kb2024-11-13 14:28:312024-11-13 14:28:33

Judging History

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

  • [2024-11-13 14:28:33]
  • 评测
  • 测评结果:TL
  • 用时:1ms
  • 内存:3776kb
  • [2024-11-13 14:28:31]
  • 提交

answer

#include<bits/stdc++.h>

#define maxn 10005
#define INF 1e18
#define int long long

using namespace std;

inline int read(){
	int lre=0,f=1;
	char c=getchar();
	while(c<'0'||c>'9'){
		if(c=='-'){
			f=-1;
		}
		c=getchar();
	}
	while(c>='0'&&c<='9'){
		lre=(lre<<3)+(lre<<1)+(c-'0');
		c=getchar();
	}
	return lre*f;
}

int n;
int arr[maxn],brr[maxn];

vector<int> v;//空闲位置集合

void del(int x){
	for(int i=0;i+1<v.size();i++){
		if(v[i]==x){
			swap(v[i],v[i+1]);
		}
	}
	if(v[v.size()-1]==x)v.pop_back();
} 

bool okay(int x,int ind){
	for(int i=1;i<=n;i++){
		if(arr[i]!=0){
			brr[i]=arr[i];
		}else if(i<ind){
			brr[i]=x-1;//[1,x-1]已知,x-1一定是错的 
		}else{
			brr[i]=x;
		}
	}
	printf("0 ");
	for(int i=1;i<=n;i++){
		printf("%lld ",brr[i]);
	}
	putchar('\n');
	fflush(stdout);
	int lre=read();
	return lre>=x;
}

void solve(int x){
	int l=0,r=v.size()-1,mid,res;
	while(l<=r){
		mid=l+r>>1;
		//认为位置v[mid]是x
		if(okay(x,v[mid])){
			res=v[mid];
			l=mid+1;
		}else{
			r=mid-1;
		}
	}
	del(res);
	arr[res]=x;
}

signed main(){
	
	n=read();
	for(int i=1;i<=n;i++){
		v.push_back(i);
	}
	
	for(int i=1;i<=n;i++)brr[i]=2;
	
	for(int i=1;i<=n;i++){
	//	cout<<"i="<<i<<"!"<<endl;
		brr[i]=1;
		printf("0 ");
		for(int j=1;j<=n;j++){
			printf("%lld ",brr[j]);
		}
		putchar('\n');
		fflush(stdout);
		int lre=read();
		if(lre==2){
			//这一位是1 
			arr[i]=1;
			del(i);
		}else if(lre==0){
			//这一位是2 
			arr[i]=2;
			del(i);
		}
		brr[i]=2;
	}//确定1的位置 
	
	for(int i=3;i<n;i++){
		solve(i);
	}
	arr[v[0]]=n;//最后剩下的位置一定是n 
	
	printf("1 ");
	for(int i=1;i<=n;i++){
		printf("%lld ",arr[i]);
	}
	putchar('\n');
	fflush(stdout);
	
	return 0;
} 
/*
二分确定每一个位置 

第一个? 


0 6 4 2 3 1 5

*/

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

input:

5
1
1
0
2
1
2
3
4
3

output:

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

result:

ok Accepted

Test #2:

score: -100
Time Limit Exceeded

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

result: