QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#306042 | #2293. Boredom Buster | linak | TL | 0ms | 0kb | C++17 | 3.8kb | 2024-01-16 10:52:46 | 2024-01-16 10:52:46 |
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];
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++){
if(k[i].size()==2){
auto p=k[i][0],q=k[i][1];
k[i].pop_back();
k[i].pop_back();
cout<<"? "<<p.second.first<<" "<<q.second.first<<endl;
int x,y;
cin>>x>>y;
if(k[p.first].size()==2 && k[p.first][0].first==i) swap(k[p.first][0],k[p.first][1]);
if(k[q.first].size()==2 && k[q.first][0].first==i) swap(k[q.first][0],k[q.first][1]);
k[p.first].pop_back();
k[q.first].pop_back();
if(x==y && y==i){
ans[p.second.first]=ans[q.second.first]=i;
ans[p.second.second]=p.first;
ans[q.second.second]=q.first;
}
else if(x==i){
ans[p.second.second]=p.first;
ans[q.second.second]=i;
k[i].push_back({q.first,{p.second.first,q.second.first}});
k[q.first].push_back({i,{p.second.first,q.second.first}});
}
else if(y==i){
ans[p.second.second]=i;
ans[q.second.second]=q.first;
k[i].push_back({p.first,{p.second.first,q.second.first}});
k[p.first].push_back({i,{p.second.first,q.second.first}});
}
else{
ans[p.second.second]=ans[q.second.second]=i;
if(k[p.first].empty() || k[p.first][0].first!=q.first){
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}});
}
}
}
}
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][0];
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){
ans[u.second.second]=u.first;
ans[s]=q;
p=i,q=p;
}
else if(x==i && y==q){
ans[u.second.second]=u.first;
ans[s]=p;
p=i;
}
else if(x==u.first && y==p){
ans[u.second.second]=i;
ans[s]=q;
p=u.first,q=p;
}else{
ans[u.second.second]=i;
ans[s]=p;
p=u.first;
}
s=r,r=u.second.first;
}
}
}
while(p!=-1){
int tx=ans[p];
cout<<"? "<<tx<<" "<<r<<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){
if(x==p) ans[r]=ans[s]=p,ans[tx]=q;
else ans[r]=ans[s]=q,ans[tx]=p;
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: 0
Time Limit Exceeded
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 ...