Submission #597137

#	Time	Username	Problem	Language	Result	Execution time	Memory
597137		ttamx	Aliens (IOI07_aliens)	C++14	70 / 100	2 ms	300 KiB

aliens

#include<bits/stdc++.h>
#define ll long long

using namespace std;

ll n,xo,yo;

bool check(ll x,ll y){
    cout << "examine " << x << " " << y << endl;
    string ret;
    cin >> ret;
    return ret=="true";
}

int main(){
    cin.tie(nullptr)->sync_with_stdio(false);
    cin >> n >> xo >> yo;
    ll l=xo,r=n;
    for(ll i=1;xo+i<=n;i<<=1){
        if(!check(xo+i,yo)){
            r=xo+i;
            break;
        }else{
            l=xo+i;
        }
    }
    while(r-1>l){
        ll m=(l+r)>>1;
        if(check(m,yo)){
            l=m;
        }else{
            r=m;
        }
    }
    ll xr=l;
    l=1,r=xo;
    for(ll i=1;xo-i>=1;i<<=1){
        if(!check(xo-i,yo)){
            l=xo-i;
            break;
        }else{
            r=xo-i;
        }
    }
    while(r-1>l){
        ll m=(l+r)>>1;
        if(check(m,yo)){
            r=m;
        }else{
            l=m;
        }
    }
    ll xl=r;
    ll sz=xr-xl+1;
    l=xr,r=n;
    for(ll i=2*sz;xr+i<=n;i<<=1){
        if(!check(xr+i,yo)){
            r=xr+i;
            break;
        }else{
            l=xr+i;
        }
    }
    while(r-sz>l){
        ll m=(l+r)>>1;
        if(check(m,yo)){
            l=m;
        }else{
            r=m;
        }
    }
    ll Xr=l;
    l=1,r=xl;
    for(ll i=2*sz;xl-i>=1;i<<=1){
        if(!check(xl-i,yo)){
            l=xl-i;
            break;
        }else{
            r=xl-i;
        }
    }
    while(r-sz>l){
        ll m=(l+r)>>1;
        if(check(m,yo)){
            r=m;
        }else{
            l=m;
        }
    }
    ll Xl=r;
    l=yo,r=n;
    for(ll i=2*sz;yo+i<=n;i<<=1){
        if(!check(Xl,yo+i)){
            r=yo+i;
            break;
        }else{
            l=yo+i;
        }
    }
    while(r-sz>l){
        ll m=(l+r)>>1;
        if(check(Xl,m)){
            l=m;
        }else{
            r=m;
        }
    }
    while(r-1>l){
        ll m=(l+r)>>1;
        if(check(Xl,m)){
            l=m;
        }else{
            r=m;
        }
    }
    ll Yr=l;
    sz=(Xr-Xl)/2;
    cout << "solution " << Xl+sz << " " << Yr-sz << endl;
}

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