Submission #53671

#	Time	Username	Problem	Language	Result	Execution time	Memory
53671		SpaimaCarpatilor	Aliens (IOI07_aliens)	C++17	100 / 100	5 ms	660 KiB

aliens

#include<bits/stdc++.h>

using namespace std;

int M, N, X, Y, up, down, lft, rgt;

bool ok (int i, int j)
{
    if (i < 1 || j < 1 || i > N || j > N) return 0;
    cout << "examine " << i << " " << j << endl;
    cout.flush ();
    char ans[109];
    cin >> ans;
    return (ans[0] == 't');
}

void finish (int i, int j)
{
    cout << "solution " << i << " " << j << endl;
    cout.flush ();
}

void detUp ()
{
    int lg = 0;
    while (ok (X - (1 << lg), Y)) lg ++;
    if (lg > 0)
        lg --, up -= (1 << lg);
    for (int i=lg - 1; i>=0; i--)
        if (ok (up - (1 << i), Y))
            up -= (1 << i);
}

void detDown ()
{
    int lg = 0;
    while (ok (X + (1 << lg), Y)) lg ++;
    if (lg > 0)
        lg --, down += (1 << lg);
    for (int i=lg - 1; i>=0; i--)
        if (ok (down + (1 << i), Y))
            down += (1 << i);
}

void detLeft ()
{
    int lg = 0;
    while (ok (X, Y - (1 << lg))) lg ++;
    if (lg > 0)
        lg --, lft -= (1 << lg);
    for (int i=lg - 1; i>=0; i--)
        if (ok (X, lft - (1 << i)))
            lft -= (1 << i);
}

void detRight ()
{
    int lg = 0;
    while (ok (X, Y + (1 << lg))) lg ++;
    if (lg > 0)
        lg --, rgt += (1 << lg);
    for (int i=lg - 1; i>=0; i--)
        if (ok (X, rgt + (1 << i)))
            rgt += (1 << i);
}

void detIJ (bool u, bool d, int &i)
{
    if (u & d) i = 2;
    else
    if (d)
    {
        if (ok (up - M, lft - M)) i = 1;
        else i = 0;
    }
    else
    {
        if (ok (up + M, lft + M)) i = 3;
        else i = 4;
    }
}

int main ()
{
cin >> N >> X >> Y;
up = X, down = X, lft = Y, rgt = Y;
detUp ();
detDown ();
detLeft ();
detRight ();
M = down - up + 1;
int i, j;
bool u = ok (up - 2 * M, lft), l = ok (up, lft - 2 * M), r = ok (up, lft + 2 * M), d = ok (up + 2 * M, rgt);
detIJ (u, d, i);
detIJ (l, r, j);
int x = up + (down - up) / 2, y = lft + (rgt - lft) / 2;
finish (x + (2 - i) * M, y + (2 - j) * M);
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