QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#417143 | #1464. Interactive Algorithm | dengziyue | TL | 1ms | 4156kb | C++14 | 1.1kb | 2024-05-22 15:14:18 | 2024-05-22 15:14:18 |
Judging History
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...