Submission #1154614

#TimeUsernameProblemLanguageResultExecution timeMemory
1154614WongYiKaiAliens (IOI07_aliens)C++20
100 / 100
0 ms432 KiB
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;


int main(){
	ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	
	ll n,x,y;
    cin >> n >> x >> y;
    ll currx = 0;
    ll time = 1;
    ll curr = 1;
    currx += curr;
    cout << "examine " << x+currx << " " << y << endl;
    string in;
    cin >> in;
    while (in=="true" && x+currx+curr <= n){
        currx += curr;
        cout << "examine " << x+currx << " " << y << endl;
        time++;
        if (time%2==1){
            curr *= 2;
        }
        cin >> in;
    }
    ll nxpos = -1;
    if (in=="false"){
        while (in=="false" && x+currx+curr <= n){
            currx += curr;
            cout << "examine " << x+currx << " " << y << endl;
            time++;
            if (time%2==1){
                curr *= 2;
            }
            cin >> in;
        }
        if (in=="true") nxpos = x+currx;
    }

    ll leftedge = -1, rightedge = -1;

    ll sz = -1;
    if (nxpos != -1){

        ll mid = x+(nxpos-x)/2;
        ll l=x,r=mid, m;
        while (l<r){
            m = l+(r-l)/2;
            cout << "examine " << m << " " << y << endl;
            cin >> in;
            if (in=="true") l=m+1;
            else r=m;
        }
        leftedge = l;
        l=mid,r=nxpos, m;
        while (l<r){
            m = l+(r-l)/2;
            cout << "examine " << m << " " << y << endl;
            cin >> in;
            if (in=="false") l=m+1;
            else r=m;
        }
        rightedge = l-1;
        sz = rightedge - leftedge+1;
    }
    else{
        ll currx = 0;
        ll time = 1;
        ll curr = 1;
        currx += curr;
        cout << "examine " << x-currx << " " << y << endl;
        cin >> in;
        while (in=="true" && x-currx-curr >=1){
            currx += curr;
            cout << "examine " << x-currx << " " << y << endl;
            time++;
            if (time%2==1){
                curr *= 2;
            }
            cin >> in;
        }
        if (in=="false"){
            while (in=="false" && x-currx-curr >= 1){
                currx += curr;
                cout << "examine " << x-currx << " " << y << endl;
                time++;
                if (time%2==1){
                    curr *= 2;
                }
                cin >> in;
            }
            if (in=="true") nxpos = x-currx;
        }
        ll mid = nxpos+(x-nxpos)/2;
        ll l=nxpos,r=mid, m;
        while (l<r){
            m = l+(r-l)/2;
            cout << "examine " << m << " " << y << endl;
            cin >> in;
            if (in=="true") l=m+1;
            else r=m;
        }
        leftedge = l;
        l=mid,r=x, m;
        while (l<r){
            m = l+(r-l)/2;
            cout << "examine " << m << " " << y << endl;
            cin >> in;
            if (in=="false") l=m+1;
            else r=m;
        }
        rightedge = l-1;
        sz = rightedge - leftedge+1;
    }

    //cout << sz << " " << nxpos;

    ll mpx = leftedge+(rightedge-leftedge)/2+sz;

    
    ll truex=-1,truey=-1;

    if (mpx+sz+sz > n) in="false";
    else{
        cout << "examine " << mpx+sz+sz << " " << y << endl;
        cin >> in;
    }

    if (in=="true"){
        truex = mpx;
    } 
    else{

        if (mpx-(sz*4) < 1) in="false";
        else{
            cout << "examine " << mpx-(sz*4) << " " << y << endl;
            cin >> in;
        }

        if (in=="true"){
            truex = mpx-(sz*2);
        } 
        else truex = mpx-sz;
    }

    cout << "examine " << truex << " " << y << endl;
    cin >> in;

    ll y2 = -1;

    if (in=="true"){
        if (y+sz*2 > n) in="false";
        else{
            cout << "examine " << truex << " " << y+sz*2 << endl;
            cin >> in;
        }
        if (in=="false"){
            y2 = y-(sz*2);
        }
        else{
            if (y-(sz*2) < 1) in="false";
            else{
                cout << "examine " << truex << " " << y-(sz*2) << endl;
                cin >> in;
            }
            if (in=="false"){
                y2 = y+sz*2;
            }
            else y2 = y;
        }
    } 
    else{

        if (y+sz*3 > n) in="false";
        else{
            cout << "examine " << truex << " " << y+sz*3 << endl;
            cin >> in;
        }

        if (in=="true"){
            y2 = y+sz;
        } 
        else y2 = y-sz;
    }

    //cout << truex << " " << y2;

    ll l=y2,r=min(y2+sz,n), m;
    while (l<r){
        m = l+(r-l)/2;
        cout << "examine " << truex << " " << m << endl;
        cin >> in;
        if (in=="true") l=m+1;
        else r=m;
    }
    ll yedge = l-1;

    truey = yedge-sz/2;

    cout << "solution " << truex << " " << truey;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...