oj.uz

Submission #550767

# Submission time Handle Problem Language Result Execution time Memory
550767 2022-04-19T06:17:27 Z Jomnoi Aliens (IOI07_aliens) C++17
100 / 100
 3 ms 248 KB 
#include <bits/stdc++.h>
#define DEBUG false
using namespace std;

long long N, X0, Y0, l, r, mid, M, leftmost, rightmost, topmost, downmost, cx, cy;
string result;

bool ask(const long long &x, const long long &y) {
    cout << "examine " << x << ' ' << y << endl;
    cin >> result;
    return result == "true";
}

int main() {
    cin.tie(nullptr)->sync_with_stdio(false);
    cin >> N >> X0 >> Y0;

    // Find right most position in the current area
    l = X0;
    for(int b = 0; b < 30; b++) {
        if(X0 + (1<<b) > N) {
            r = N;
            break;
        }
        if(ask(X0 + (1<<b), Y0) == false) {
            r = X0 + (1<<b);
            break;
        }
    }
    while(l <= r) {
        mid = (l + r) / 2;

        if(ask(mid, Y0) == true) {
            l = mid + 1;
            rightmost = mid;
        }
        else {
            r = mid - 1;
        }
    }

    // Find left most position in the current area
    r = X0;
    for(int b = 0; b < 30; b++) {
        if(X0 - (1<<b) < 1) {
            l = 1;
            break;
        }
        if(ask(X0 - (1<<b), Y0) == false) {
            l = X0 - (1<<b);
            break;
        }
    }
    while(l <= r) {
        mid = (l + r) / 2;

        if(ask(mid, Y0) == true) {
            r = mid - 1;
            leftmost = mid;
        }
        else {
            l = mid + 1;
        }
    }

    M = rightmost - leftmost + 1;

    // Find the top most position in the current area
    l = Y0;
    for(int b = 0; b < 30; b++) {
        if(Y0 + (1<<b) > N) {
            r = N;
            break;
        }
        if(ask(X0, Y0 + (1<<b)) == false) {
            r = Y0 + (1<<b);
            break;
        }
    }
    while(l <= r) {
        mid = (l + r) / 2;

        if(ask(X0, mid) == true) {
            l = mid + 1;
            topmost = mid;
        }
        else {
            r = mid - 1;
        }
    }

    downmost = topmost - M + 1;

    cx = (leftmost + rightmost) / 2;
    cy = (topmost + downmost) / 2;

    // Find the lowest left area
    while(cx - M >= 1 and cy - M >= 1 and ask(cx - M, cy - M) == true) {
        cx -= M;
        cy -= M;
    }
    while(cx - 2 * M >= 1 and ask(cx - 2 * M, cy) == true) {
        cx -= 2 * M;
    }
    while(cy - 2 * M >= 1 and ask(cx, cy - 2 * M) == true) {
        cy -= 2 * M;
    }

    cx += 2 * M;
    cy += 2 * M;

    cout << "solution " << cx << ' ' << cy << endl;
    return 0;
}

Subtask #1
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 #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 2 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 1 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 248 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 1 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 2 ms 208 KB Output is correct

Subtask #9
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 208 KB Output is correct
2 Correct 2 ms 208 KB Output is correct
3 Correct 1 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 1 ms 208 KB Output is correct
3 Correct 2 ms 208 KB Output is correct