Submission #596070

#	Time	Username	Problem	Language	Result	Execution time	Memory
596070		mosiashvililuka	Aliens (IOI07_aliens)	C++14	100 / 100	3 ms	208 KiB

aliens

#include<bits/stdc++.h>
using namespace std;
long long a,b,c,d,e,i,j,ii,jj,zx,xc,lef,rig,mid,X1,X2,Y1,Y2,X,Y,mnX,mxX,mnY,mxY,M,x;
bool chk(long long q, long long w){
    if(q<=0||q>a||w<=0||w>a) return 0;
    string qw;
    cout<<"examine "<<q<<" "<<w<<endl;
    cin>>qw;
    if(qw[0]=='t') return 1; else return 0;
}
bool ask(long long q, long long w){
    return chk(q,w);
}
int main(){
    ios_base::sync_with_stdio(false),cin.tie(0),cout.tie(0);
    cin>>a>>i>>j;

    //
    while(1){
        if(ask(i,j-1)==0){
            Y1=j;break;
        }

        x=1;d=j-1;
        while(1){
            c=d-x;
            if(c<=0){
                lef=0;rig=d;
                break;
            }
            if(ask(i,c)==0){
                lef=c;rig=d;
                break;
            }
            d=c;x*=2;
        }

        while(1){
            if(lef+1>=rig) break;
            mid=(lef+rig)/2;
            if(ask(i,mid)==1){
                rig=mid;
            }else{
                lef=mid;
            }
        }
        Y1=rig;
        break;
    }
    //cout<<"Y1: "<<Y1;exit(0);
    //

    while(1){
        if(ask(i,j+1)==0){
            Y2=j;break;
        }
        x=1;d=j+1;
        while(1){
            c=d+x;
            if(c>a){
                lef=d;rig=a+1;
                break;
            }
            if(ask(i,c)==0){
                lef=d;rig=c;
                break;
            }
            d=c;x*=2;
        }

        while(1){
            if(lef+1>=rig) break;
            mid=(lef+rig)/2;
            if(ask(i,mid)==1){
                lef=mid;
            }else{
                rig=mid;
            }
        }
        Y2=lef;
        break;
    }

    M=Y2-Y1+1;
    //
    lef=max(0LL,i-M);rig=i;
    while(1){
        if(lef+1>=rig) break;
        mid=(lef+rig)/2;
        if(chk(mid,j)==1){
            rig=mid;
        }else{
            lef=mid;
        }
    }
    X1=rig;
    lef=i;rig=min(a+1,i+M);
    while(1){
        if(lef+1>=rig) break;
        mid=(lef+rig)/2;
        if(chk(mid,j)==1){
            lef=mid;
        }else{
            rig=mid;
        }
    }
    X2=lef;
    //
    //cout<<"Borders: "<<X1<<" "<<X2<<"   "<<Y1<<" "<<Y2<<"\n";


    X=(X1+X2)/2;Y=(Y1+Y2)/2;
    M=X2-X1+1;

    mnX=5;mxX=-5;
    mnY=5;mxY=-5;
    for(i=-4; i<=4; i++){
        for(j=-4; j<=4; j++){
            if((i+8)%2!=(j+8)%2) continue;
            if(chk(X+i*M,Y+j*M)==1){
                mnX=min(mnX,i);mxX=max(mxX,i);
                mnY=min(mnY,j);mxY=max(mxY,j);
            }else{

            }
        }
    }
    c=(mnX+mxX)/2;
    d=(mnY+mxY)/2;
    i=X+c*M;
    j=Y+d*M;
    cout<<"solution "<<i<<" "<<j<<endl;
    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