QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#306122#2293. Boredom BusterlinakWA 166ms7692kbC++175.8kb2024-01-16 14:02:402024-01-16 14:02:41

Judging History

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

  • [2024-01-16 14:02:41]
  • 评测
  • 测评结果:WA
  • 用时:166ms
  • 内存:7692kb
  • [2024-01-16 14:02:40]
  • 提交

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++){
        if(k[i].size()==2){
            auto p=k[i][0],q=k[i][1];
            k[i].pop_back();
            k[i].pop_back();

            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();

            while(true){
                cout<<"? "<<p.second.first<<" "<<q.second.first<<endl;
                int x,y;
                cin>>x>>y;

                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;
                    break;
                }
                else if(x!=i && y!=i){
                    ans[p.second.second]=ans[q.second.second]=i;
                    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}});
                    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==i) {
                                ans[p.second.first]=ans[p.second.second]=i;
                                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]=i;
                            }
                            break;
                        }
                        continue;
                    }
                    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}});
                    break;
                }else{
                    if(p.first==q.first){
                        cout<<"? "<<p.second.first<<" "<<p.second.second<<endl;
                        cin>>x>>y;
                        if(x==y){
                            if(x==i) {
                                ans[p.second.first]=ans[p.second.second]=i;
                                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]=i;
                            }
                            break;
                        }
                        continue;
                    }
                    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}});
                    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: 0
Wrong Answer
time: 166ms
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:

wrong answer Wrong answer: Too many guesses: 92322 (which is 322 over).