QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#306181#2293. Boredom BusterlinakWA 169ms7692kbC++176.0kb2024-01-16 14:50:222024-01-16 14:50:22

Judging History

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

  • [2024-01-16 14:50:22]
  • 评测
  • 测评结果:WA
  • 用时:169ms
  • 内存:7692kb
  • [2024-01-16 14:50:22]
  • 提交

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).