oj.uz

Submission #53671

# Submission time Handle Problem Language Result Execution time Memory
53671 2018-06-30T18:02:29 Z SpaimaCarpatilor Aliens (IOI07_aliens) C++17
100 / 100
 5 ms 660 KB 
#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.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 380 KB Output is correct
2 Correct 2 ms 380 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 380 KB Output is correct
2 Correct 2 ms 380 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 380 KB Output is correct
2 Correct 3 ms 380 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 440 KB Output is correct
2 Correct 2 ms 472 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 472 KB Output is correct
2 Correct 2 ms 472 KB Output is correct

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 472 KB Output is correct
2 Correct 3 ms 528 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 528 KB Output is correct
2 Correct 3 ms 660 KB Output is correct
3 Correct 3 ms 660 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 660 KB Output is correct
2 Correct 3 ms 660 KB Output is correct
3 Correct 4 ms 660 KB Output is correct

Subtask #9
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 660 KB Output is correct
2 Correct 4 ms 660 KB Output is correct
3 Correct 2 ms 660 KB Output is correct

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 660 KB Output is correct
2 Correct 3 ms 660 KB Output is correct
3 Correct 3 ms 660 KB Output is correct