QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#306038#2293. Boredom BusterlinakTL 0ms0kbC++173.8kb2024-01-16 10:46:132024-01-16 10:46:14

Judging History

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

  • [2024-01-16 10:46:14]
  • 评测
  • 测评结果:TL
  • 用时:0ms
  • 内存:0kb
  • [2024-01-16 10:46:13]
  • 提交

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];
    for(int i=1; i<=a/2; i++){
        cout<<"? "<<2*i-1<<" "<<2*i<<endl;
        int x,y;
        cin>>x>>y;
        k[x].push_back({y,{2*i-1,2*i}});
        k[y].push_back({x,{2*i-1,2*i}});
    }

    int ans[a+1];
    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 ...

result: