QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#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;
}

详细

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