Submission #1184138

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

aliens

#include <bits/stdc++.h>

using namespace std;

#define ll long long

ll n;

int ask(ll x, ll 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() {
    ll x, y;
    cin >> n >> x >> y;
    ll sz = 3, cur = 0;
    ll l = x, r = x;
    while (1) {
        ll pos = x + sz + cur;
        ll 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) {
        ll mid = (l + r) / 2;
        ll get = ask(mid, y);
        if (get) l = mid;
        else r = mid;
    }
    ll rightSide = l;
    sz = 3, cur = 0;
    l = r = x;
    while (1) {
        ll pos = x - sz - cur;
        ll 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) {
        ll mid = (l + r) / 2;
        ll get = ask(mid, y);
        if (get) r = mid;
        else l = mid;
    }
    ll leftSide = r;
    ll sqSize = rightSide - leftSide + 1;
    l = y, r = y + sqSize;
    while (l + 1 < r) {
        ll mid = (l + r) / 2;
        ll get = ask(x, mid);
        if (get) l = mid;
        else r = mid;
    }
    ll topSide = l, botSide = l - sqSize + 1;
    ll centerX = leftSide + sqSize / 2, centerY = botSide + sqSize / 2;
    ll cnt = 1;
    ll 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) {
        ll get = ask(centerX + 2 * sqSize, centerY);
        ll bigPosX = 3;
        if (get) {
            bigPosX--;
            get = ask(centerX + 4 * sqSize, centerY);
            if (get) bigPosX--;
        }
        ll 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 {
        ll get = ask(centerX + 2 * sqSize, centerY);
        ll bigPosX = 3;
        if (get) bigPosX -= 2;
        ll 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: 10 / 10
• Subtask 10: 10 / 10