oj.uz

Submission #697190

# Submission time Handle Problem Language Result Execution time Memory
697190 2023-02-08T18:21:19 Z ThegeekKnight16 Aliens (IOI07_aliens) C++17
100 / 100
 3 ms 208 KB 
#include <bits/stdc++.h>
using namespace std;
int N;
int cnt = 0;
#define int long long

bool query(int x, int y)
{
    if (x < 1 || x > N) return false;
    if (y < 1 || y > N) return false;
    cnt++;
    assert(cnt <= 300);
    cout << "examine " << x << " " << y << endl;
    string resp;
    cin >> resp;
    return (resp == "true");
}

int32_t main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int X0, Y0;
    cin >> N >> X0 >> Y0;


    int Xdir = X0, Xesq = X0;
    for (int k = 30; k >= 0; k--)
    {
        assert(cnt <= 300);
        if (!query(Xdir + (1 << k), Y0)) continue;
        if (k > 0 && !query(Xdir + (1 << (k-1)), Y0)) {k--; continue;}
        if (k > 1 && !query(Xdir + (1 << (k-2)), Y0)) {k -= 2; continue;}
        Xdir += (1 << k);
    }
    assert(cnt <= 300);
    // cerr << "Xdir = " << Xdir << endl;
    for (int k = 30; k >= 0; k--)
    {
        assert(cnt <= 300);
        if (!query(Xesq - (1 << k), Y0)) continue;
        if (k > 0 && !query(Xesq - (1 << (k-1)), Y0)) {k--; continue;}
        if (k > 1 && !query(Xesq - (1 << (k-2)), Y0)) {k -= 2; continue;}
        Xesq -= (1 << k);
    }
    assert(cnt <= 300);
    // cerr << "Xesq = " << Xesq << endl;

    int Ydir = Y0, Yesq = Y0;
    for (int k = 30; k >= 0; k--)
    {
        assert(cnt <= 300);
        if (!query(X0, Ydir + (1 << k))) continue;
        if (k > 0 && !query(X0, Ydir + (1 << (k - 1)))) {k--; continue;}
        if (k > 1 && !query(X0, Ydir + (1 << (k - 2)))) {k -= 2; continue;}
        Ydir += (1 << k);
    }
    assert(cnt <= 300);
    // cerr << "Ydir = " << Ydir << endl;
    for (int k = 30; k >= 0; k--)
    {
        assert(cnt <= 300);
        if (!query(X0, Yesq - (1 << k))) continue;
        if (k > 1 && !query(X0, Yesq - (1 << (k - 2)))) {k -= 2; continue;}
        if (k > 0 && !query(X0, Yesq - (1 << (k - 1)))) {k--; continue;}
        Yesq -= (1 << k);
    }
    assert(cnt <= 300);
    // cerr << "Yesq = " << Yesq << endl;

    int X = (Xesq + Xdir + 1) / 2;
    int Y = (Yesq + Ydir + 1) / 2;
    int M = (Xdir - Xesq + 1);
    // cerr << X << " " << Y << " " << M << endl;
    // cerr << "found M: " << M << endl;
    int Xresp = X; int Yresp = Y;

    if (query(X + (4*M), Y)) Xresp += (2 * M);
    else if (query(X - (4*M), Y)) Xresp -= (2 * M);
    else
    {
        bool b1 = query(X - (2*M), Y);
        bool b2 = query(X + (2*M), Y);
        if (b1 && !b2) Xresp -= M;
        else if (!b1 && b2) Xresp += M;
    }

    assert(cnt <= 300);

    if (query(X, Y + (4*M))) Yresp += (2*M);
    else if (query(X, Y - (4*M))) Yresp -= (2*M);
    else
    {
        bool b1 = query(X, Y - (2*M));
        bool b2 = query(X, Y + (2*M));
        if (b1 && !b2) Yresp -= M;
        else if (!b1 && b2) Yresp += M;
    }
    assert(cnt <= 300);

    cout << "solution " << Xresp << " " << Yresp << endl;
}

Subtask #1
10.0 / 10.0

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

Subtask #2
10.0 / 10.0

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

Subtask #3
10.0 / 10.0

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

Subtask #4
10.0 / 10.0

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

Subtask #5
10.0 / 10.0

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

Subtask #6
10.0 / 10.0

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

Subtask #7
10.0 / 10.0

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

Subtask #8
10.0 / 10.0

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

Subtask #9
10.0 / 10.0

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

Subtask #10
10.0 / 10.0

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