oj.uz

Submission #484839

# Submission time Handle Problem Language Result Execution time Memory
484839 2021-11-05T15:27:00 Z Alexandruabcde Aliens (IOI07_aliens) C++14
100 / 100
 4 ms 304 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+1, dr = Y0 + putere - 1;
    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+1, dr = Y0-1;
    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;
    }

    Y0 = Y_Down;
    return Y_Up - Y_Down + 1;
}

pair <LL, LL> FindCorner (LL M, LL X0, LL Y0) {
    pair <LL, LL> ans;
    ans.second = Y0;
    LL putere = 1;
    for (; Question(X0-putere, Y0); putere<<=1);
    LL st = X0-putere+1, dr = X0-1;
    ans.first = 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;
    }

    pair <LL, LL> sol = ans;
    for (int i = -4; i <= 4; ++ i )
        for (int j = -4; j <= 4; ++ j ) {
            pair <LL, LL> aux = {ans.first + i * M, ans.second + j * M};

            bool val = Question(aux.first, aux.second);

            if (!val) continue;

            if (aux.first < sol.first) sol = aux;
            else if (aux.first == sol.first && aux.second < sol.second) sol = aux;
        }

    return sol;
}

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 + (M/2) << " " << Corner_int.second + 2 * M_int + (M/2) << '\n';
    return 0;
}

Subtask #1
10.0 / 10.0

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

Subtask #2
10.0 / 10.0

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

Subtask #3
10.0 / 10.0

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

Subtask #4
10.0 / 10.0

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

Subtask #5
10.0 / 10.0

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

Subtask #6
10.0 / 10.0

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

Subtask #7
10.0 / 10.0

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

Subtask #8
10.0 / 10.0

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

Subtask #9
10.0 / 10.0

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

Subtask #10
10.0 / 10.0

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