Submission #1339052

#	Time	Username	Problem	Language	Result	Execution time	Memory
1339052		ma_moutahid	Aliens (IOI07_aliens)	C++20	100 / 100	1 ms	412 KiB

aliens

#include<bits/stdc++.h>

using namespace std;

using ll=long long;
#define int ll

int n,X0,Y0,lb,rb,x,y,m;

const int MAX=2e9;

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

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


int dx[]={1,-1,0,-0};
int dy[]={0,0,1,-1};


int bs(int x, int y, int dir, int bound ){
    int l=0;
    int r=bound;
    while(r>l){
        int mid=(l+r+1)/2;
        int u=x+dx[dir]*mid;
        int v=y+dy[dir]*mid;
        if(query(u,v))l=mid;
        else r=mid-1;
    }
    return r;
}


void get_small_center(){
    int right=1,left=1;
    while(query(X0+right,Y0))right*=2;
    while(query(X0-left,Y0))left*=2;
    int tr=bs(X0,Y0,0,right);    
    int tl=bs(X0,Y0,1,left);    
    m=tr+tl+1;
    x=X0-tl+m/2;
    int tu=bs(X0,Y0,2,m);

    y=Y0+tu-m/2;
}


signed main(){
    cin>>n>>X0>>Y0;
    
    get_small_center();

    while(query(x-m,y-m)){
        x-=m;
        y-=m;
    }
    while(query(x-2*m,y)){
        x-=2*m;
    }
    while(query(x,y-2*m))y-=2*m;
    x+=2*m;
    y+=2*m;
    answer(x,y);


}

• 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