Submission #1184136

#	Time	Username	Problem	Language	Result	Execution time	Memory
1184136		alterio	Aliens (IOI07_aliens)	C++20	80 / 100	1 ms	416 KiB

aliens

#include <bits/stdc++.h>

using namespace std;

int n;

int ask(int x, int y) {
    if (x < 1 || x > n || y < 1 || y > n) return 0;
    cout << "examine " << x << " " << y << endl;
    string res;
    cin >> res;
    return (res == "true");
}

int main() {
    int x, y;
    cin >> n >> x >> y;
    int sz = 3, cur = 0;
    int l = x, r = x;
    while (1) {
        int pos = x + sz + cur;
        int get = ask(pos, y);
        if (get) {
            l = x + sz + cur;
            cur += sz;
            sz = cur + (cur % 2 == 0);
        }
        else {
            r = x + sz + cur;
            break;
        }
    }
    while (l + 1 < r) {
        int mid = (l + r) / 2;
        int get = ask(mid, y);
        if (get) l = mid;
        else r = mid;
    }
    int rightSide = l;
    sz = 3, cur = 0;
    l = r = x;
    while (1) {
        int pos = x - sz - cur;
        int get = ask(pos, y);
        if (get) {
            r = x - sz - cur;
            cur += sz;
            sz = cur + (cur % 2 == 0);
        }
        else {
            l = x - sz - cur;
            break;
        }
    }
    while (l + 1 < r) {
        int mid = (l + r) / 2;
        int get = ask(mid, y);
        if (get) r = mid;
        else l = mid;
    }
    int leftSide = r;
    int sqSize = rightSide - leftSide + 1;
    l = y, r = y + sqSize;
    while (l + 1 < r) {
        int mid = (l + r) / 2;
        int get = ask(x, mid);
        if (get) l = mid;
        else r = mid;
    }
    int topSide = l, botSide = l - sqSize + 1;
    int centerX = leftSide + sqSize / 2, centerY = botSide + sqSize / 2;
    int cnt = 1;
    int get = ask(centerX + 2 * sqSize, centerY);
    if (get) cnt++;
    get = ask(centerX + 4 * sqSize, centerY);
    if (get) cnt++;
    get = ask(centerX - 2 * sqSize, centerY);
    if (get) cnt++;
    get = ask(centerX - 4 * sqSize, centerY);
    if (get) cnt++;
    if (cnt == 3) {
        int get = ask(centerX + 2 * sqSize, centerY);
        int bigPosX = 3;
        if (get) {
            bigPosX--;
            get = ask(centerX + 4 * sqSize, centerY);
            if (get) bigPosX--;
        }
        int bigPosY = 3;
        get = ask(centerX, centerY + 2 * sqSize);
        if (get) {
            bigPosY--;
            get = ask(centerX, centerY + 4 * sqSize);
            if (get) bigPosY--;
        }
        cout << "solution " << centerX + (2 - bigPosX) * 2 * sqSize << " " << centerY + (2 - bigPosY) * 2 * sqSize << endl;
    }
    else {
        int get = ask(centerX + 2 * sqSize, centerY);
        int bigPosX = 3;
        if (get) bigPosX -= 2;
        int bigPosY = 3;
        get = ask(centerX, centerY + 2 * sqSize);
        if (get) bigPosY -= 2;
        cout << "solution " << centerX + (2 - bigPosX) * sqSize << " " << centerY + (2 - bigPosY) * sqSize << endl; 
    }
}

• 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: 0 / 10
• Subtask 10: 0 / 10