oj.uz

Submission #484825

# Submission time Handle Problem Language Result Execution time Memory
484825 2021-11-05T14:54:01 Z Alexandruabcde Aliens (IOI07_aliens) C++14
0 / 100
 4 ms 200 KB 
#include <bits/stdc++.h>

using namespace std;

typedef long long LL;

LL N, X0, Y0;

bool Question (LL X, LL Y) {
    if (X < 1 || X > N || Y < 1 || Y > N) return 0;

    cout << "examine " << X << " " << Y << '\n';
    string ans;

    cin >> ans;

    if (ans == "true") return 1;

    return 0;
}

LL FindM (LL X0, LL Y0) {
    LL putere = 1;

    for (; Question(X0, Y0+putere); putere<<=1);

    LL st = Y0, dr = Y0 + putere;
    LL Y_Up = Y0;

    while (st <= dr) {
        LL mij = (st + dr) / 2;
        bool val = Question(X0, mij);
        if (val) {
            Y_Up = mij;
            st = mij + 1;
        }
        else dr = mij - 1;
    }

    putere = 1;
    for (; Question(X0, Y0-putere); putere<<=1);

    st = Y0-putere, dr = Y0;
    LL Y_Down = Y0;

    while (st <= dr) {
        LL mij = (st + dr) / 2;
        bool val = Question(X0, mij);
        if (val) {
            Y_Down = mij;
            dr = mij - 1;
        }
        else st = mij + 1;
    }

    return Y_Up - Y_Down + 1;
}

pair <LL, LL> FindCorner (LL M, LL X0, LL Y0) {
    pair <LL, LL> ans;

    LL putere = 1;
    for (; Question(X0, Y0-putere); putere<<=1);
    LL st = Y0-putere, dr = Y0;
    while (st <= dr) {
        LL mij = (st + dr) / 2;
        bool val = Question(X0, mij);
        if (val) {
            ans.second = mij;
            dr = mij - 1;
        }
        else st = mij + 1;
    }

    putere = 1;
    for (; Question(X0-putere, Y0); putere<<=1);
    st = X0-putere, dr = X0;
    while (st <= dr) {
        LL mij = (st + dr) / 2;
        bool val = Question(mij, Y0);
        if (val) {
            ans.first = mij;
            dr = mij - 1;
        }
        else st = mij + 1;
    }

    bool val = 1;
    while (Question(ans.first - M, ans.second - M) == val) {
        ans.first -= M;
        ans.second -= M;
    }

    val = Question(ans.first, ans.second);
    while (Question(ans.first, ans.second-M) != val) {
        ans.second -= M;
        val = Question(ans.first, ans.second);
    }
    ans.second += M;

    val = Question(ans.first, ans.second);
    while (Question(ans.first-M, ans.second) != val) {
        ans.first -= M;
        val = Question(ans.first, ans.second);
    }
    ans.first += M;

    return ans;
}

int main () {
    cin >> N >> X0 >> Y0;

    LL M = FindM(X0, Y0);
    pair <LL, LL> Corner = FindCorner(M, X0, Y0);

    int M_int = (int)M;
    pair <int, int> Corner_int = Corner;

    cout << "solution " << Corner_int.first + 2 * M_int + 1 << " " << Corner_int.second + 2 * M_int + 1 << '\n';
    return 0;
}

Subtask #1
0 / 10.0

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

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 200 KB Incorrect
2 Halted 0 ms 0 KB -

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 200 KB Incorrect
2 Halted 0 ms 0 KB -

Subtask #4
0 / 10.0

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

Subtask #5
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 200 KB Incorrect
2 Halted 0 ms 0 KB -

Subtask #6
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 200 KB Incorrect
2 Halted 0 ms 0 KB -

Subtask #7
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 200 KB Incorrect
2 Halted 0 ms 0 KB -

Subtask #8
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 200 KB Incorrect
2 Halted 0 ms 0 KB -

Subtask #9
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 4 ms 200 KB Incorrect
2 Halted 0 ms 0 KB -

Subtask #10
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 200 KB Incorrect
2 Halted 0 ms 0 KB -