Submission #1176673

#TimeUsernameProblemLanguageResultExecution timeMemory
117667312345678Aliens (IOI07_aliens)C++17
100 / 100
0 ms412 KiB
#include <bits/stdc++.h>

using namespace std;

#define ll long long

const int kx=31;

ll n, x, y, mnx, mxx, mny, mxy, m;
string str;

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

int main()
{
    cin>>n>>x>>y;
    mnx=x, mxx=x;
    for (int i=kx-1; i>=0; i--) if (query(mnx-(1<<i), y)) mnx=mnx-(1<<i);
    for (int i=kx-1; i>=0; i--) if (query(mxx+(1<<i), y)) mxx=mxx+(1<<i); 
    if (query((mnx+mxx)/2, y))
    {
        ll tmp=(mxx-mnx+1);
        if (query(mxx+2*tmp, y)||query(mxx-2*tmp, y)) m=tmp;
        else m=tmp/5;
    }
    else m=(mxx-mnx+1)/3;
    while (query(mnx-2*m, y)) mnx=mnx-2*m;
    while (query(mxx+2*m, y)) mxx=mxx+2*m;
    mny=y, mxy=y;
    for (int i=kx-1; i>=0; i--) if (query(x, mny-(1<<i))) mny=mny-(1<<i);
    for (int i=kx-1; i>=0; i--) if (query(x, mxy+(1<<i))) mxy=mxy+(1<<i);
    while (query(x, mny-2*m)) mny=mny-2*m;
    while (query(x, mxy+2*m)) mxy=mxy+2*m;
    cout<<"solution "<<(mnx+mxx)/2<<' '<<(mny+mxy)/2<<endl;
}
#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...