Submission #412397

#	Time	Username	Problem	Language	Result	Execution time	Memory
412397		Dakto	Aliens (IOI07_aliens)	C++17	70 / 100	5 ms	296 KiB

aliens

#include <bits/stdc++.h>
using namespace std;

bool query(int x, int y){
    cout<<"examine "<<x<<" "<<y<<endl;
    string s;
    cin>>s;
    return s=="true";
}

int main(){
    int n,x,y;
    cin>>n>>x>>y;

    //find right bound
    int l=x, r=n;
    while(l<r){
        int m=(l+r+1)/2;
        if(query(m,y)) l=m;
        else r=m-1;
    }

    if(!query((x+l)/2,y)){
        r=(x+l)/2;
        l=x;
        while(l<r){
            int m=(l+r+1)/2;
            if(query(m,y)) l=m;
            else r=m-1;
        }
    }
    int rb=l;

    l=1, r=x;
    while(l<r){
        int m=(l+r)/2;
        if(query(m,y)) r=m;
        else l=m+1;
    }

    if(!query((x+l)/2,y)){
        l=(x+l)/2;
        r=x;
        while(l<r){
            int m=(l+r)/2;
            if(query(m,y)) r=m;
            else l=m+1;
        }
    }
    int lb=l;

    l=y, r=n;
    while(l<r){
        int m=(l+r+1)/2;
        if(query(x,m)) l=m;
        else r=m-1;
    }

    if(!query(x,(y+l)/2)){
        r=(y+l)/2;
        l=y;
        while(l<r){
            int m=(l+r+1)/2;
            if(query(x,m)) l=m;
            else r=m-1;
        }
    }
    int db=l;

    l=1, r=y;
    while(l<r){
        int m=(l+r)/2;
        if(query(x,m)) r=m;
        else l=m+1;
    }

    if(!query(x,(y+l)/2)){
        l=(y+l)/2;
        r=y;
        while(l<r){
            int m=(l+r)/2;
            if(query(x,m)) r=m;
            else l=m+1;
        }
    }
    int ub=l;

    cerr<<lb<<endl<<rb<<endl<<ub<<endl<<db<<endl;

    int cx=(lb+rb)/2, cy=(ub+db)/2, d=rb-lb+1;

    cerr<<cx<<endl<<cy<<endl<<d<<endl;

    bool up=cy+2*d<=n?query(cx,cy+2*d):0;
    bool down=cy-2*d>0?query(cx,cy-2*d):0;
    bool left=cx-2*d>0?query(cx-2*d,cy):0;
    bool right=cx+2*d<=n?query(cx+2*d,cy):0;

    if(up && down && left && right){
        cout<<"solution "<<cx<<" "<<cy<<endl;
        return 0;
    }
    if(down+up+left+right==3){
        if(!down){
            cout<<"solution "<<cx<<" "<<cy+2*d<<endl;
        }
        if(!up){
            cout<<"solution "<<cx<<" "<<cy-2*d<<endl;
        }
        if(!left){
            cout<<"solution "<<cx+2*d<<" "<<cy<<endl;
        }
        if(!right){
            cout<<"solution "<<cx-2*d<<" "<<cy<<endl;
        }
        return 0;
    }
    if(down && right){
        if(cx + 4*d<=n && query(cx+4*d,cy)){
            cout<<"solution "<<cx+2*d<<" "<<cy-2*d<<endl;
        } 
        else{
            cout<<"solution "<<cx+d<<" "<<cy-d<<endl;
        }
    }

    if(down && left){
        if(cx - 4*d>0 && query(cx-4*d,cy)){
            cout<<"solution "<<cx-2*d<<" "<<cy-2*d<<endl;
        } 
        else{
            cout<<"solution "<<cx-d<<" "<<cy-d<<endl;
        }
    }
    if(up && right){
        if(cx + 4*d<=n && query(cx+4*d,cy)){
            cout<<"solution "<<cx+2*d<<" "<<cy+2*d<<endl;
        } 
        else{
            cout<<"solution "<<cx+d<<" "<<cy+d<<endl;
        }
    }
    if(up && left){
        if(cx - 4*d>0 && query(cx-4*d,cy)){
            cout<<"solution "<<cx-2*d<<" "<<cy+2*d<<endl;
        } 
        else{
            cout<<"solution "<<cx-d<<" "<<cy+d<<endl;
        }
    }
}

• 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: 0 / 10
• Subtask 9: 0 / 10
• Subtask 10: 0 / 10