QOJ.ac

QOJ

ID	题目	提交者	结果	用时	内存	语言	文件大小	提交时间	测评时间
#730936	#9570. Binary Tree	wxgmjfhy	WA	2ms	3896kb	C++20	3.4kb	2024-11-09 22:31:50	2024-11-09 22:31:50

Judging History

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

[2024-11-09 22:31:50]
评测

测评结果：WA
用时：2ms
内存：3896kb

查看

[2024-11-09 22:31:50]
提交

answer

#include<bits/stdc++.h>
using namespace std;
// #pragma GCC optimize(3)
#define int long long

// std::mt19937_64 rng {std::chrono::steady_clock::now().time_since_epoch().count()};

// #define LOCAL

int x,cnt;

inline int query(int a,int b){
    cnt++;

    cout<<"? "<<a<<" "<<b<<endl;
    cin>>x;
    return x;
}

int n;

inline void solve(){
    cin>>n;

    cnt=0;
    int lim=log2(n);

    vector<int>ls(n+1),rs(n+1),p(n+1);

    for(int i=1;i<=n;i++){
        cin>>ls[i]>>rs[i];
        if(ls[i])p[ls[i]]=i;
        if(rs[i])p[rs[i]]=i;
    }

    int rt=-1;
    for(int i=1;i<=n;i++){
        if(!p[i])rt=i;
    }

    int now=rt;
    while(1){
        if(!ls[now]&&!rs[now]){
            if(cnt==lim){
                cout<<"! "<<now<<endl;
                return;
            }

            vector<int>v(1);

            int pos=now;
            while(1){
                v.push_back(pos);
                int fa=p[pos];
                if(!fa||(ls[fa]&&rs[fa]))break;
                pos=fa;
            }

            int m=v.size()-1;

            int l=1,r=m;
            while(1){
                int x=query(v[l],v[r]);

                if(x==0){
                    if(l+1==r){
                        cout<<"! "<<v[l]<<endl;
                        return;
                    }
                    r=l+r>>1;
                }else if(x==2){
                    if(l+1==r){
                        cout<<"! "<<v[r]<<endl;
                        return;
                    }
                    l=l+r>>1;
                }else{
                    assert(r-l&1^1);
                    cout<<"! "<<v[r+l>>1]<<endl;
                    return;
                }
            }
        }

        if(!ls[now]){
            now=rs[now];
            continue;
        }

        if(!rs[now]){
            now=ls[now];
            continue;
        }

        int x=query(ls[now],rs[now]);

        if(x==0){
            now=ls[now];
        }else if(x==2){
            now=rs[now];
        }else{
            if(cnt==lim){
                cout<<"! "<<now<<endl;
                return;
            }
            
            vector<int>v(1);

            int pos=now;
            while(1){
                v.push_back(pos);
                int fa=p[pos];
                if(!fa||(ls[fa]&&rs[fa]))break;
                pos=fa;
            }

            int m=v.size()-1;

            int l=1,r=m;
            while(1){
                int x=query(v[l],v[r]);

                if(x==0){
                    if(l+1==r){
                        cout<<"! "<<v[l]<<endl;
                        return;
                    }
                    r=l+r>>1;
                }else if(x==2){
                    if(l+1==r){
                        cout<<"! "<<v[r]<<endl;
                        return;
                    }
                    l=l+r>>1;
                }else{
                    assert(r-l&1^1);
                    cout<<"! "<<v[r+l>>1]<<endl;
                    return;
                }
            }
        }
    }
}

signed main(){
    ios::sync_with_stdio(false);
    cin.tie(0);

    #ifdef LOCAL
    freopen("in.txt","r",stdin);
    freopen("out.txt","w",stdout);
    #endif

    // cout<<setiosflags(ios::fixed)<<setprecision(10);

    int _=1;
    cin>>_;
    while(_--){
        solve();
    }
    return 0;
}

源文件, 语言: C++20

详细

Test #1:

score: 100

Accepted

time: 0ms

memory: 3896kb

input:

output:

result:

ok OK (2 test cases)

Test #2:

score: -100

Wrong Answer

time: 2ms

memory: 3696kb

input:

output:

result:

wrong answer There are 2 candidates. (test case 3)