Submission #992448

#	Time	Username	Problem	Language	Result	Execution time	Memory
992448		The_Samurai	Aliens (IOI07_aliens)	C++17	100 / 100	2 ms	344 KiB

aliens

// I stand with PALESTINE




// #pragma GCC optimize("Ofast,O3")
// #pragma GCC target("avx,avx2")
#include "bits/stdc++.h"

using namespace std;
using ll = long long;
#define int long long

map<pair<int, int>, bool> mp;

int n;
bool query(int x, int y) {
    if (mp.count({x, y})) return mp[{x, y}];
    assert(1 <= x and x <= n);
    assert(1 <= y and y <= n);
    cout << "examine " << x << ' ' << y << endl;
    string s;
    cin >> s;
    mp[{x, y}] = s == "true";
    return mp[{x, y}];
}

void answer(int x, int y) {
    cout << "solution " << x << ' ' << y << endl;
    exit(0);
}

void solve() {
    int x0, y0;
    cin >> n >> x0 >> y0;
    int lx, rx, l, r, best;
    lx = 0, rx = 1;
    while (true) {
        if (x0 - rx <= 0) {
            rx = x0 - 1;
            break;
        }
        if (query(x0 - rx, y0)) {
            lx = rx;
            rx *= 2;
        } else {
            rx--;
            break;
        }
    }
    while (lx <= rx) {
        int mid = (lx + rx) >> 1;
        if (query(x0 - mid, y0)) {
            l = x0 - mid;
            lx = mid + 1;
        } else {
            rx = mid - 1;
        }
    }
    lx = 0, rx = 1;
    while (true) {
        if (x0 + rx > n) {
            rx = n - x0;
            break;
        }
        if (query(x0 + rx, y0)) {
            lx = rx;
            rx *= 2;
        } else {
            rx--;
            break;
        }
    }
    while (lx <= rx) {
        int mid = (lx + rx) >> 1;
        if (query(x0 + mid, y0)) {
            r = x0 + mid;
            lx = mid + 1;
        } else {
            rx = mid - 1;
        }
    }
    x0 = (l + r) / 2;
    int m = r - l + 1;
    lx = 0, rx = min(m, y0) - 1;
    while (lx <= rx) {
        int mid = (lx + rx) >> 1;
        if (query(x0, y0 - mid)) {
            best = y0 - mid;
            lx = mid + 1;
        } else {
            rx = mid - 1;
        }
    }
    y0 = best + m / 2;
    vector<pair<int, int>> variants;
    for (int i = 1; i <= 5; i++) {
        for (int j = 1; j <= 5; j++) {
            if (i % 2 != j % 2) continue;
            auto [x, y] = make_pair(x0, y0);
            x += (3 - i) * m;
            y += (3 - j) * m;
            if (x - 2 * m < 1 or x + 2 * m > n or y - 2 * m < 1 or y + 2 * m > n) continue;
            bool ok = true;
            if (!query(x - 2 * m, y - 2 * m)) continue;
            if (!query(x + 2 * m, y + 2 * m)) continue;
            answer(x, y);
        }
    }
}

int32_t main() {
    cin.tie(0)->sync_with_stdio(false);
// #ifdef sunnatov
//     freopen("input.txt", "r", stdin);
//     freopen("output.txt", "w", stdout);
// #endif
    int q = 1;
    // cin >> q;
    while (q--) {
        solve();
        cout << '\n';
    }
}

Compilation message (stderr)

aliens.cpp: In function 'void solve()':
aliens.cpp:104:18: warning: unused variable 'ok' [-Wunused-variable]
  104 |             bool ok = true;
      |                  ^~
aliens.cpp:95:15: warning: 'best' may be used uninitialized in this function [-Wmaybe-uninitialized]
   95 |     y0 = best + m / 2;
      |          ~~~~~^~~~~~~
aliens.cpp:84:15: warning: 'r' may be used uninitialized in this function [-Wmaybe-uninitialized]
   84 |     int m = r - l + 1;
      |             ~~^~~
aliens.cpp:84:15: warning: 'l' may be used uninitialized in this function [-Wmaybe-uninitialized]

• 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