QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#417143#1464. Interactive AlgorithmdengziyueTL 1ms4156kbC++141.1kb2024-05-22 15:14:182024-05-22 15:14:18

Judging History

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

  • [2024-05-22 15:14:18]
  • 评测
  • 测评结果:TL
  • 用时:1ms
  • 内存:4156kb
  • [2024-05-22 15:14:18]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;
#define max_n 400
int n;
int p[max_n+2];
bool can[max_n+2][max_n+2];
int now;
struct E{int v,nx;}e[max_n*2+2];
int ei=0,fir[max_n+2];
int de[max_n+2];
vector<int>ans;
inline void addedge(int u,int v){e[++ei]=(E){v,fir[u]}; fir[u]=ei; ++de[u];}
void dfs(int u,int f){
	ans.push_back(u);
	for(int i=fir[u],v;i;i=e[i].nx){
		v=e[i].v;
		if(v!=f)dfs(v,u);
	}
}
int main(){
	srand(time(0));
	scanf("%d",&n);
	for(int i=1;i<=n;++i)p[i]=i;
	memset(can,1,sizeof(can));
	now=n*(n-1)/2;
	while(now>n-1){
		random_shuffle(p+1,p+n+1);
		printf("? ");
		for(int i=1;i<=n;++i)printf("%d ",p[i]);
		printf("\n"); fflush(stdout);
		int x; scanf("%d",&x);
		if(!x){
			for(int i=1;i<n;++i){
				if(can[p[i]][p[i+1]]){can[p[i]][p[i+1]]=can[p[i+1]][p[i]]=false; --now;}
			}
		}
	}
	for(int i=1;i<=n;++i){
		for(int j=i+1;j<=n;++j){
			if(can[i][j]){addedge(i,j); addedge(j,i);}
		}
	}
	for(int u=1;u<=n;++u){
		if(de[u]==1){dfs(u,0); break;}
	}
	printf("! ");
	for(auto u:ans)printf("%d ",u);
	printf("\n");
	return 0;
}

详细

Test #1:

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

input:

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

output:

? 4 2 5 3 1 
? 2 4 5 1 3 
? 1 3 4 2 5 
? 1 4 2 5 3 
? 4 2 5 1 3 
? 5 2 1 4 3 
? 5 4 3 1 2 
? 4 3 2 1 5 
? 2 4 1 5 3 
? 5 3 2 1 4 
? 1 5 3 4 2 
? 1 3 2 4 5 
? 5 1 3 4 2 
? 5 2 4 1 3 
? 5 3 2 1 4 
? 4 3 5 1 2 
? 3 1 4 5 2 
? 3 2 4 1 5 
? 2 4 5 1 3 
? 1 5 2 3 4 
? 3 1 2 5 4 
? 4 2 5 3 1 
? 5 4 2 1 3 
?...

result:

ok n=5, 67 queries

Test #2:

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

input:

2

output:

! 1 2 

result:

ok n=2, 0 queries

Test #3:

score: -100
Time Limit Exceeded

input:

3
2
1
2
2
1
2
1
2
1
2
2
1
2
2
1
1
2
1
1
2
1
1
2
2
1
1
2
1
1
1
1
1
2
2
2
1
2
1
2
1
1
1
1
2
1
2
1
2
2
2
1
1
1
1
1
2
1
2
1
1
1
1
1
2
2
2
1
2
2
2
1
1
1
1
2
1
2
2
1
1
2
2
1
1
1
1
1
2
1
2
1
1
2
1
2
2
1
2
1
2
1
2
1
1
1
1
2
2
1
1
1
1
2
2
2
2
1
1
1
1
1
1
2
1
1
1
1
1
2
2
1
1
1
2
1
1
2
1
1
2
2
1
1
1
1
1
1
1
1
...

output:

? 3 2 1 
? 2 3 1 
? 3 2 1 
? 1 2 3 
? 1 3 2 
? 3 2 1 
? 3 1 2 
? 1 2 3 
? 2 3 1 
? 3 2 1 
? 1 2 3 
? 3 1 2 
? 3 2 1 
? 3 2 1 
? 2 1 3 
? 2 1 3 
? 3 2 1 
? 2 3 1 
? 1 3 2 
? 3 2 1 
? 1 3 2 
? 3 1 2 
? 3 2 1 
? 3 2 1 
? 1 3 2 
? 1 3 2 
? 1 2 3 
? 2 3 1 
? 2 1 3 
? 2 3 1 
? 1 3 2 
? 1 3 2 
? 3 2 1 
? 3...

result: