QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#306181 | #2293. Boredom Buster | linak | WA | 169ms | 7692kb | C++17 | 6.0kb | 2024-01-16 14:50:22 | 2024-01-16 14:50:22 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
int a;
cin>>a;
vector<pair<int,pii>> k[a+1];
vector<int> ans(a+1);
for(int i=1; i<=a/2; i++){
cout<<"? "<<2*i-1<<" "<<2*i<<endl;
int x,y;
cin>>x>>y;
if(x==y){
ans[2*i-1]=ans[2*i]=x;
continue;
}
k[x].push_back({y,{2*i-1,2*i}});
k[y].push_back({x,{2*i-1,2*i}});
}
for(int i=1; i<=a/2; i++){
int t=i;
while(k[t].size()==2){
auto p=k[t][0],q=k[t][1];
k[t].pop_back();
k[t].pop_back();
if(k[p.first].size()==2 && k[p.first][0].first==t) swap(k[p.first][0],k[p.first][1]);
if(k[q.first].size()==2 && k[q.first][0].first==t) swap(k[q.first][0],k[q.first][1]);
k[p.first].pop_back();
k[q.first].pop_back();
while(true){
cout<<"? "<<p.second.first<<" "<<q.second.first<<endl;
int x,y;
cin>>x>>y;
if(x==y && y==t){
ans[p.second.first]=ans[q.second.first]=t;
ans[p.second.second]=p.first;
ans[q.second.second]=q.first;
if(!k[p.first].empty()) t=k[p.first][0].first;
break;
}
else if(x!=t && y!=t){
ans[p.second.second]=ans[q.second.second]=t;
if(p.first==q.first){
ans[p.second.first]=ans[q.second.first]=p.first;
break;
}
k[p.first].push_back({q.first,{p.second.first,q.second.first}});
k[q.first].push_back({p.first,{p.second.first,q.second.first}});
t=p.first;
break;
}
else if(x==q.first || y==q.first){
if(p.first==q.first){
cout<<"? "<<p.second.first<<" "<<p.second.second<<endl;
cin>>x>>y;
if(x==y){
if(x==t) {
ans[p.second.first]=ans[p.second.second]=t;
ans[q.second.first]=ans[q.second.second]=p.first;
}else{
ans[p.second.first]=ans[p.second.second]=p.first;
ans[q.second.first]=ans[q.second.second]=t;
}
break;
}
continue;
}
ans[p.second.second]=p.first;
ans[q.second.second]=t;
k[t].push_back({q.first,{p.second.first,q.second.first}});
k[q.first].push_back({t,{p.second.first,q.second.first}});
if(!k[p.first].empty()) t=k[p.first][0].first;
break;
}else{
if(p.first==q.first){
cout<<"? "<<p.second.first<<" "<<p.second.second<<endl;
cin>>x>>y;
if(x==y){
if(x==t) {
ans[p.second.first]=ans[p.second.second]=t;
ans[q.second.first]=ans[q.second.second]=p.first;
}else{
ans[p.second.first]=ans[p.second.second]=p.first;
ans[q.second.first]=ans[q.second.second]=t;
}
break;
}
continue;
}
ans[p.second.second]=t;
ans[q.second.second]=q.first;
k[t].push_back({p.first,{p.second.first,q.second.first}});
k[p.first].push_back({t,{p.second.first,q.second.first}});
t=p.first;
break;
}
}
}
}
int p=-1,q=-1,r=-1,s=-1;
for(int i=1; i<=a/2; i++){
if(!k[i].empty()){
auto u=k[i].back();
k[u.first].pop_back();
if(p==-1) p=i,q=u.first,r=u.second.first,s=u.second.second;
else{
cout<<"? "<<u.second.first<<" "<<r<<endl;
int x,y;
cin>>x>>y;
if((x==i && y==p) || (x==p && y==i)){
ans[u.second.second]=u.first;
ans[s]=q;
q=p,p=i;
}
else if((x==i && y==q) || (x==q && y==i)){
ans[u.second.second]=u.first;
ans[s]=p;
p=i;
}
else if((x==u.first && y==p) || (x==p && y==u.first)){
ans[u.second.second]=i;
ans[s]=q;
q=p,p=u.first;
}else{
ans[u.second.second]=i;
ans[s]=p;
p=u.first;
}
s=r,r=u.second.first;
}
}
}
int u=0;
if(p!=-1){
for(int i=1; i<=a; i++){
if(ans[i]==p){
u=i;
break;
}
}
}
while(p!=-1){
cout<<"? "<<r<<" "<<u<<endl;
int x,y;
cin>>x>>y;
if(x==y){
if(x==p) ans[r]=p,ans[s]=q;
else ans[r]=q,ans[s]=p;
break;
}else{
cout<<"? "<<r<<" "<<s<<endl;
cin>>x>>y;
if(x==y){
ans[r]=ans[s]=p,ans[u]=q;
break;
}
}
}
cout<<"! ";
for(int i=1; i<=a; i++) cout<<ans[i]<<" ";
cout<<endl;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 148ms
memory: 7692kb
input:
100000 14243 13962 6948 22252 19244 19543 38903 11287 38236 8431 8855 44004 32239 28696 4163 13408 34466 26456 34636 16506 17476 19659 41596 45165 44174 8145 32853 13855 13860 32650 39829 40439 26857 16321 28351 11239 14823 35976 18843 47987 13886 18541 1370 15381 16164 41277 10418 10077 1431 40902 ...
output:
? 1 2 ? 3 4 ? 5 6 ? 7 8 ? 9 10 ? 11 12 ? 13 14 ? 15 16 ? 17 18 ? 19 20 ? 21 22 ? 23 24 ? 25 26 ? 27 28 ? 29 30 ? 31 32 ? 33 34 ? 35 36 ? 37 38 ? 39 40 ? 41 42 ? 43 44 ? 45 46 ? 47 48 ? 49 50 ? 51 52 ? 53 54 ? 55 56 ? 57 58 ? 59 60 ? 61 62 ? 63 64 ? 65 66 ? 67 68 ? 69 70 ? 71 72 ? 73 74 ? 75 76 ? 77 ...
result:
ok Queries used: 91890
Test #2:
score: -100
Wrong Answer
time: 169ms
memory: 7492kb
input:
100000 41874 17281 40541 23499 2411 12273 46034 10695 9169 29627 12031 28270 45783 2390 6091 49751 46029 45662 38649 48940 33046 6151 33047 4151 26515 11802 35711 9780 39443 38890 10137 3418 14295 6609 22808 1819 30599 9883 31665 21226 25409 49659 7103 4428 12488 49739 24656 47502 13155 33362 23201 ...
output:
? 1 2 ? 3 4 ? 5 6 ? 7 8 ? 9 10 ? 11 12 ? 13 14 ? 15 16 ? 17 18 ? 19 20 ? 21 22 ? 23 24 ? 25 26 ? 27 28 ? 29 30 ? 31 32 ? 33 34 ? 35 36 ? 37 38 ? 39 40 ? 41 42 ? 43 44 ? 45 46 ? 47 48 ? 49 50 ? 51 52 ? 53 54 ? 55 56 ? 57 58 ? 59 60 ? 61 62 ? 63 64 ? 65 66 ? 67 68 ? 69 70 ? 71 72 ? 73 74 ? 75 76 ? 77 ...
result:
wrong answer Wrong answer: Too many guesses: 92030 (which is 30 over).