Submission #550767

#	Time	Username	Problem	Language	Result	Execution time	Memory
550767		Jomnoi	Aliens (IOI07_aliens)	C++17	100 / 100	3 ms	248 KiB

aliens

#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 / 10
• Subtask 2: 10 / 10
• Subtask 3: 10 / 10
• Subtask 4: 10 / 10
• Subtask 5: 10 / 10
• Subtask 6: 10 / 10
• Subtask 7: 10 / 10
• Subtask 8: 10 / 10
• Subtask 9: 10 / 10
• Subtask 10: 10 / 10