QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#411111 | #1464. Interactive Algorithm | jqdai0724 | ML | 62ms | 3612kb | C++17 | 1.7kb | 2024-05-14 22:59:05 | 2024-05-14 22:59:05 |
Judging History
answer
// what is matter? never mind.
//#pragma GCC optimize("Ofast")
//#pragma GCC optimize("unroll-loops")
//#pragma GCC target("sse,sse2,sse3,sse4,popcnt,abm,mmx,avx,avx2")
#include<bits/stdc++.h>
#define For(i,a,b) for(int i=(a);i<=(b);++i)
#define Rep(i,a,b) for(int i=(a);i>=(b);--i)
#define ll long long
#define ull unsigned long long
using namespace std;
inline int read()
{
char c=getchar();int x=0;bool f=0;
for(;!isdigit(c);c=getchar())f^=!(c^45);
for(;isdigit(c);c=getchar())x=(x<<1)+(x<<3)+(c^48);
if(f)x=-x;return x;
}
#define fi first
#define se second
#define pb push_back
#define mkp make_pair
typedef pair<int,int>pii;
typedef vector<int>vi;
#define maxn 200005
#define inf 0x3f3f3f3f
int n,p[maxn];
mt19937_64 rnd(114514);
bool e[405][405];
int deg[405];
void dfs(int u,int pa){
cout<<u<<" ";
For(v,1,n)
if(v!=pa && e[u][v])dfs(v,u);
}
signed main()
{
cin>>n;
For(i,1,n)p[i]=i;
For(i,1,n)deg[i]=n-1;
For(i,1,n)For(j,i+1,n)e[i][j]=e[j][i]=1;
For(_,1,8000){
shuffle(p+1,p+n+1,rnd);
cout<<"? ";
For(i,1,n)cout<<p[i]<<" ";cout<<endl;
int x;cin>>x;
if(x==n-1){
cout<<"! ";
For(i,1,n)cout<<p[i]<<" ";cout<<endl;
exit(0);
}
if(x==0){
For(i,1,n-1)
if(e[p[i]][p[i+1]])
e[p[i]][p[i+1]]=e[p[i+1]][p[i]]=0,--deg[p[i]],--deg[p[i+1]];
// bool ok=1;
// For(i,1,n)
// if(deg[i]>2){ok=0;break;}
//// For(i,1,n)cout<<deg[i]<<" ";puts("");
//// For(i,1,n)For(j,1,n)cout<<e[i][j]<<" \n"[j==n];
// if(ok){
// cout<<"! ";
// For(i,1,n)if(deg[i]==1)dfs(i,0),cout<<endl,exit(0);
// assert(0);
// }
}
}
cout<<"! ";
For(i,1,n)if(deg[i]==1)dfs(i,0),exit(0);
return 0;
}
/*
1 2 3 4
*/
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 1ms
memory: 3608kb
input:
5 0 1 2 2 1 3 2 2 1 3 1 1 1 2 2 2 2 3 0 4
output:
? 4 1 2 3 5 ? 5 3 2 4 1 ? 5 2 3 4 1 ? 4 3 1 2 5 ? 4 5 1 2 3 ? 2 4 3 5 1 ? 1 3 4 5 2 ? 3 5 2 4 1 ? 2 4 5 3 1 ? 2 5 1 3 4 ? 4 1 3 2 5 ? 2 3 1 5 4 ? 1 2 3 4 5 ? 3 1 5 4 2 ? 4 3 2 1 5 ? 5 2 4 1 3 ? 1 3 4 5 2 ? 4 2 5 1 3 ? 1 4 5 3 2 ? 3 4 2 5 1 ! 3 4 2 5 1
result:
ok n=5, 20 queries
Test #2:
score: 0
Accepted
time: 1ms
memory: 3612kb
input:
2 1
output:
? 2 1 ! 2 1
result:
ok n=2, 1 queries
Test #3:
score: 0
Accepted
time: 0ms
memory: 3544kb
input:
3 1 2
output:
? 3 1 2 ? 1 2 3 ! 1 2 3
result:
ok n=3, 2 queries
Test #4:
score: 0
Accepted
time: 0ms
memory: 3548kb
input:
4 3
output:
? 3 1 4 2 ! 3 1 4 2
result:
ok n=4, 1 queries
Test #5:
score: 0
Accepted
time: 1ms
memory: 3556kb
input:
5 0 1 1 2 1 3 2 1 2 3 1 2 1 3 2 2 2 3 0 3 2 2 2 0 2 1 3 2 0 2 0 2 3 3 2 0 1 2 1 0 2 2 3 1 2 1 2 2 3 0 2 3 2 3 3 2 1 0 1 1 2 2 0 1 1 0 2 1 2 1 2 1 0 3 0 1 1 2 2 2 2 3 2 2 2 1 0 2 2 2 0 0 2 2 0 2 1 2 1 2 1 1 0 1 1 1 2 1 3 1 2 2 1 4
output:
? 4 1 2 3 5 ? 5 3 2 4 1 ? 5 2 3 4 1 ? 4 3 1 2 5 ? 4 5 1 2 3 ? 2 4 3 5 1 ? 1 3 4 5 2 ? 3 5 2 4 1 ? 2 4 5 3 1 ? 2 5 1 3 4 ? 4 1 3 2 5 ? 2 3 1 5 4 ? 1 2 3 4 5 ? 3 1 5 4 2 ? 4 3 2 1 5 ? 5 2 4 1 3 ? 1 3 4 5 2 ? 4 2 5 1 3 ? 1 4 5 3 2 ? 3 4 2 5 1 ? 5 4 3 1 2 ? 2 4 1 3 5 ? 2 4 1 5 3 ?...
result:
ok n=5, 114 queries
Test #6:
score: 0
Accepted
time: 0ms
memory: 3540kb
input:
7 1 0 1 1 2 2 1 1 2 3 4 0 2 4 2 2 3 0 3 1 2 1 0 2 3 2 3 2 0 3 2 3 2 1 1 1 2 4 2 2 2 2 2 2 0 1 1 1 4 2 1 3 1 2 3 1 2 2 2 1 2 3 0 0 2 2 2 3 2 0 2 3 1 3 2 1 0 4 2 2 2 4 2 4 2 3 0 1 0 1 1 2 3 1 2 1 4 2 0 1 2 2 2 2 1 1 4 0 2 1 2 3 2 2 2 1 1 2 3 3 1 3 1 1 0 1 1 2 3 3 1 0 2 1 3 1 3 3 1 4 0 4 2 3 0 1 3 1 0 ...
output:
? 4 1 6 3 5 2 7 ? 1 6 3 4 5 7 2 ? 4 3 2 6 1 7 5 ? 7 6 3 2 1 5 4 ? 1 5 6 2 7 3 4 ? 2 1 3 5 6 7 4 ? 2 7 6 5 1 4 3 ? 3 4 2 5 6 7 1 ? 7 3 4 6 5 2 1 ? 2 6 5 3 1 7 4 ? 1 5 2 3 6 4 7 ? 2 1 6 7 3 5 4 ? 7 2 6 5 1 4 3 ? 1 3 5 2 6 7 4 ? 6 3 2 5 4 7 1 ? 6 4 2 1 5 7 3 ? 2 6 3 5 1 4 7 ? 4 5 3 2 1...
result:
ok n=7, 1018 queries
Test #7:
score: 0
Accepted
time: 11ms
memory: 3528kb
input:
10 2 1 1 1 4 3 2 2 2 1 2 1 3 1 5 2 1 3 0 0 0 2 1 2 1 1 2 1 4 3 1 2 0 2 2 2 0 2 3 1 5 2 1 1 1 1 1 2 1 3 2 3 1 1 6 3 2 2 0 4 1 1 6 3 1 0 2 2 2 3 0 0 0 2 1 2 2 1 3 3 0 0 0 2 1 2 3 2 2 1 2 1 2 3 2 1 0 2 2 3 2 0 2 3 1 3 1 2 1 3 1 0 2 0 3 1 3 2 2 3 1 1 2 0 0 3 1 1 1 1 0 2 1 4 1 1 1 2 3 2 5 3 1 2 2 1 1 1 1...
output:
? 3 7 6 2 4 5 10 1 8 9 ? 4 7 9 3 5 6 10 8 2 1 ? 9 3 2 6 4 10 5 7 8 1 ? 1 6 10 9 5 4 7 3 8 2 ? 6 8 2 5 1 4 10 9 7 3 ? 7 5 10 8 9 6 4 1 2 3 ? 4 8 10 1 9 2 3 7 6 5 ? 6 10 8 7 3 2 1 4 9 5 ? 8 10 7 5 3 4 6 2 9 1 ? 2 6 8 4 3 1 10 7 9 5 ? 5 4 9 8 2 3 7 6 1 10 ? 5 8 1 2 7 9 10 6 3 4 ? 2 1 8 10 5...
result:
ok n=10, 8000 queries
Test #8:
score: 0
Accepted
time: 21ms
memory: 3472kb
input:
20 3 2 1 1 3 3 0 5 2 1 1 2 2 2 3 2 3 3 2 1 4 2 4 1 1 2 0 2 2 1 2 1 2 5 4 1 3 4 2 3 2 3 1 2 1 3 4 1 0 2 5 3 3 2 3 2 0 2 3 1 1 2 4 2 0 2 1 0 2 1 3 5 2 2 1 2 0 0 3 2 2 3 1 2 1 2 3 5 0 1 4 1 0 1 3 3 5 2 2 0 4 2 2 2 1 1 1 2 2 0 3 2 1 1 2 3 2 3 3 0 2 2 1 0 0 2 1 2 0 5 1 4 3 1 3 2 1 5 1 0 0 4 3 1 1 2 3 2 2...
output:
? 3 7 16 2 18 20 12 1 8 14 11 10 6 9 13 19 15 4 17 5 ? 16 6 8 11 3 12 19 13 1 14 10 15 4 18 7 9 17 2 20 5 ? 6 5 20 3 16 2 17 11 19 13 10 1 15 7 18 4 8 12 14 9 ? 9 3 14 11 7 19 10 6 2 5 8 4 1 12 20 16 13 15 18 17 ? 4 3 13 5 1 6 9 19 2 10 16 15 7 20 11 8 12 18 14 17 ? 10 20 2 8 4 14 16 15 6 9 11 ...
result:
ok n=20, 8000 queries
Test #9:
score: 0
Accepted
time: 10ms
memory: 3568kb
input:
30 0 2 1 1 1 1 3 1 7 4 3 0 0 1 5 3 2 3 3 3 2 3 2 2 2 1 6 3 0 0 2 2 3 3 3 2 1 0 3 1 4 1 1 2 2 1 2 3 1 1 2 1 0 1 1 2 0 3 2 2 1 0 3 2 3 0 6 4 3 0 0 0 2 1 2 1 3 3 3 2 1 2 1 3 0 1 3 3 4 2 1 0 1 3 2 1 2 3 0 1 2 3 3 1 2 3 2 3 1 2 3 1 1 2 1 2 1 1 2 3 3 0 2 4 2 2 3 3 3 2 4 1 3 3 0 1 2 2 3 1 0 3 2 2 1 2 1 2 1...
output:
? 3 7 16 23 18 24 12 22 8 29 28 10 6 9 13 19 30 25 17 5 27 1 2 20 26 4 11 21 14 15 ? 29 23 17 14 12 15 6 1 8 11 3 13 20 5 28 22 10 30 24 27 16 4 25 19 7 26 9 21 2 18 ? 27 14 24 1 25 8 21 29 15 26 10 16 19 30 9 12 11 20 28 6 22 5 4 13 7 23 2 3 17 18 ? 23 21 11 8 28 6 19 9 17 1 25 10 22 29 5 27 12 ...
result:
ok n=30, 8000 queries
Test #10:
score: 0
Accepted
time: 12ms
memory: 3592kb
input:
50 2 2 2 4 4 6 3 0 4 1 4 4 1 2 5 0 4 2 2 3 2 2 4 0 2 0 3 2 1 3 2 0 4 3 1 2 2 3 1 1 1 2 1 4 1 0 1 1 1 1 2 1 3 3 1 1 0 1 2 4 3 4 3 4 2 1 0 2 0 2 1 2 2 3 1 2 3 3 3 3 2 5 0 3 2 1 1 3 1 2 3 3 4 4 2 4 3 0 0 2 3 2 1 3 4 3 1 3 1 2 2 3 1 4 0 5 1 2 0 2 2 3 2 0 1 4 3 1 3 4 1 2 3 5 2 3 1 1 1 1 1 4 3 3 3 1 3 3 3...
output:
? 32 7 44 33 18 24 49 36 47 42 28 31 41 9 13 19 46 35 17 5 27 1 43 20 26 37 11 21 14 15 10 3 23 4 40 45 34 30 25 39 6 29 2 48 22 38 8 50 12 16 ? 47 21 15 14 45 32 23 8 44 42 19 50 37 2 13 41 4 11 16 30 49 29 18 33 1 27 28 46 9 35 20 10 24 3 40 48 25 6 31 17 22 38 7 26 34 36 12 39 43 5 ? 42 25 27 3...
result:
ok n=50, 8000 queries
Test #11:
score: 0
Accepted
time: 62ms
memory: 3612kb
input:
123 1 2 1 2 1 3 2 0 4 2 1 3 1 2 4 1 2 2 2 1 8 0 0 2 2 2 4 2 0 0 6 3 3 2 0 1 4 2 3 2 2 1 2 0 2 2 0 3 2 5 2 2 3 5 3 3 2 2 1 0 3 3 0 2 0 4 3 0 2 3 3 3 2 3 4 2 2 2 0 1 2 3 1 1 5 3 7 1 5 2 6 2 3 3 1 0 1 1 0 4 3 4 1 1 5 1 7 1 2 0 1 1 1 1 3 3 0 0 1 1 4 0 3 2 0 2 0 5 1 3 1 2 1 2 2 4 3 1 1 6 0 4 2 3 2 1 3 3 ...
output:
? 9 21 19 34 68 17 60 50 80 48 99 32 108 76 55 98 84 36 93 95 1 79 65 103 110 45 38 67 59 6 94 12 7 29 2 123 61 89 11 27 102 81 105 82 23 85 88 52 104 78 106 77 31 25 8 83 49 75 24 13 113 20 35 57 66 101 91 112 71 43 40 87 5 4 28 15 30 47 116 54 72 70 118 90 107 62 33 111 121 86 73 122 26 41 100 10 ...
result:
ok n=123, 8000 queries
Test #12:
score: -100
Memory Limit Exceeded
input:
185 4 0 1 0 1 1 4 2 1 2 6 3 3 0 1 6 1 1 1 2 5 1 1 1 2 2 1 1 1 1 1 1 1 0 3 0 4 2 5 3 2 3 1 1 2 5 6 2 2 2 4 4 1 0 1 6 4 2 2 4 0 5 3 2 2 1 3 1 3 0 1 0 6 5 2 0 1 1 2 2 1 1 1 2 3 2 0 0 1 2 3 1 2 2 2 1 1 0 2 0 3 3 1 2 5 4 3 1 1 3 3 2 1 2 0 4 1 1 1 4 2 3 2 1 2 2 1 2 3 3 3 1 1 2 1 1 1 1 2 1 2 1 3 0 0 0 2 3 ...
output:
? 9 153 162 34 68 138 60 50 80 48 169 32 108 172 156 98 84 36 154 141 1 79 65 103 110 182 38 67 157 149 94 143 7 29 2 123 61 148 180 27 102 81 105 82 23 85 88 166 104 78 124 77 31 168 8 83 134 175 161 13 113 20 35 57 174 144 91 112 176 140 128 87 5 4 28 170 181 47 116 54 179 70 118 90 155 164 145 11...