Submission #551608

#	Time	Username	Problem	Language	Result	Execution time	Memory
551608		krit3379	Aliens (IOI07_aliens)	C++17	100 / 100	4 ms	208 KiB

aliens

#include<bits/stdc++.h>
using namespace std;
#define N 5005
#define ll long long

int a[5][5];
ll n;

bool query(int x,int y){
    if(x<1||y<1||x>n||y>n)return false;
    string s;
    cout<<"examine "<<x<<" "<<y<<endl;
    cin>>s;
    return s[0]=='t';
}

void sol(int x,int y){
    cout<<"solution "<<x<<" "<<y<<endl;
}

void jump(ll x,ll y,ll di,ll dj,ll &xx,ll &yy){
    ll lx,ly,i,l,r,mid;
    lx=x,ly=y;
    for(i=0;0<x&&x<=n&&0<y&&y<=n;i++){
        x+=(1<<i)*di;
        x=min(x,n+1);
        x=max(x,0ll);
        y+=(1<<i)*dj;
        y=min(y,n+1);
        y=max(y,0ll);
        if(!query(x,y))break;
        lx=x;
        ly=y;
    }
    if(y==ly){
        if(lx<x){
            l=lx+1,r=x-1;
            while(l<=r){
                mid=(l+r)/2;
                if(query(mid,y))lx=mid,l=mid+1;
                else r=mid-1;
            }
        }
        else{
            l=x+1,r=lx-1;
            while(l<=r){
                mid=(l+r)/2;
                if(query(mid,y))lx=mid,r=mid-1;
                else l=mid+1;
            }
        }
    }
    else{
        l=y+1,r=ly-1;
        while(l<=r){
            mid=(l+r)/2;
            if(query(x,mid))ly=mid,r=mid-1;
            else l=mid+1;
        }
    }
    xx=lx,yy=ly;
}

int main(){
    ios_base::sync_with_stdio(false);cin.tie(nullptr);
    ll i,j,m,x,y,xr,yr,xl,yl,xd,yd,xc,yc,cnt=0;
    cin>>n>>x>>y;
    jump(x,y,1,0,xr,yr);
    jump(x,y,-1,0,xl,yl);
    jump(x,y,0,-1,xd,yd);
    m=xr-xl+1;
    xc=(xl+xr)/2;
    yc=yd+m/2;
    for(i=-2;i<=2;i++)for(j=-2;j<=2;j++)a[i+2][j+2]=query(xc+j*m,yc+i*m),cnt+=a[i+2][j+2];
    if(cnt==13)sol(xc,yc);
    else if(cnt==8){
        if(a[0][2]+a[4][2]+a[2][0]+a[2][4]==2){
            if(a[0][0])sol(xc-m,yc-m);
            else if(a[0][4])sol(xc+m,yc-m);
            else if(a[4][0])sol(xc-m,yc+m);
            else if(a[4][4])sol(xc+m,yc+m);
        }
        else{
            if(!a[0][2])sol(xc,yc+2*m);
            else if(!a[4][2])sol(xc,yc-2*m);
            else if(!a[2][0])sol(xc+2*m,yc);
            else if(!a[2][4])sol(xc-2*m,yc);
        }
    }
    else if(cnt==5){
        if(a[0][0])sol(xc-2*m,yc-2*m);
        else if(a[0][4])sol(xc+2*m,yc-2*m);
        else if(a[4][0])sol(xc-2*m,yc+2*m);
        else if(a[4][4])sol(xc+2*m,yc+2*m);
    }
    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