Submission #1188432

#	Time	Username	Problem	Language	Result	Execution time	Memory
1188432		North1304	Aliens (IOI07_aliens)	C++20	100 / 100	1 ms	432 KiB

aliens

#include <bits/extc++.h>
using namespace std;
typedef long long ll;
int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    ll n,x0,y0;
    if(!(cin>>n>>x0>>y0)) return 0;
    auto ask=[&](ll x,ll y){
        cout<<"examine "<<x<<' '<<y<<endl;
        cout.flush();
        string s;
        cin>>s;
        return s[0]=='t';
    };
    ll y=y0,l=x0,step=1;
    while(true){
        ll nx=l-step;
        if(nx<1) break;
        if(ask(nx,y)) l=nx,step<<=1;
        else break;
    }
    ll lo=max(1LL,l-step),hi=l;
    while(lo<hi){
        ll mid=(lo+hi)/2;
        if(ask(mid,y)) hi=mid;
        else lo=mid+1;
    }
    ll left=hi;
    ll r=x0;step=1;
    while(true){
        ll nx=r+step;
        if(nx>n) break;
        if(ask(nx,y)) r=nx,step<<=1;
        else break;
    }
    ll hf=min(n,r+step);lo=r;
    while(lo<hf){
        ll mid=(lo+hf+1)/2;
        if(ask(mid,y)) lo=mid;
        else hf=mid-1;
    }
    ll right=lo,m=right-left+1,x=x0,b=y0;step=1;
    while(true){
        ll ny=b-step;
        if(ny<1) break;
        if(ask(x,ny)) b=ny,step<<=1;
        else break;
    }
    lo=max(1LL,b-step);hi=b;
    while(lo<hi){
        ll mid=(lo+hi)/2;
        if(ask(x,mid)) hi=mid;
        else lo=mid+1;
    }
    ll bottom=hi,t=y0;step=1;
    while(true){
        ll ny=t+step;
        if(ny>n) break;
        if(ask(x,ny)) t=ny,step<<=1;
        else break;
    }
    hf=min(n,t+step);lo=t;
    while(lo<hf){
        ll mid=(lo+hf+1)/2;
        if(ask(x,mid)) lo=mid;
        else hf=mid-1;
    }
    ll top=lo,cx0=(left+right)/2,cy0=(bottom+top)/2;
    vector<pair<ll,ll>> d={{m,m},{m,-m},{-m,m},{-m,-m}};
    unordered_set<unsigned long long> vis;
    queue<pair<ll,ll>> q;
    auto enc=[&](ll x,ll y){return (unsigned long long)x<<32|y;};
    q.emplace(cx0,cy0);
    vis.insert(enc(cx0,cy0));
    ll mnx=cx0,mxx=cx0,mny=cy0,mxy=cy0;
    while(!q.empty()){
        auto [cx,cy]=q.front();q.pop();
        for(auto [dx,dy]:d){
            ll nx=cx+dx,ny=cy+dy;
            if(nx<1||nx>n||ny<1||ny>n) continue;
            auto code=enc(nx,ny);
            if(vis.count(code)) continue;
            if(ask(nx,ny)){
                vis.insert(code);
                q.emplace(nx,ny);
                mnx=min(mnx,nx);
                mxx=max(mxx,nx);
                mny=min(mny,ny);
                mxy=max(mxy,ny);
            }
        }
    }
    ll xc=(mnx+mxx)/2,yc=(mny+mxy)/2;
    cout<<"solution "<<xc<<' '<<yc<<endl;
    cout.flush();
    return 0;
}

• Subtask 1: 10 / 10
• Subtask 2: 10 / 10
• Subtask 3: 10 / 10
• Subtask 4: 10 / 10
• Subtask 5: 10 / 10
• Subtask 6: 10 / 10
• Subtask 7: 10 / 10
• Subtask 8: 10 / 10
• Subtask 9: 10 / 10
• Subtask 10: 10 / 10