Submission #1154561

#TimeUsernameProblemLanguageResultExecution timeMemory
1154561itslqAliens (IOI07_aliens)C++20
30 / 100
1 ms416 KiB
#include <bits/stdc++.h>
using namespace std;

int cx, cy, s, N;
map<int, map<int, bool>> memo;

bool query(int x, int y) {
    cout << "examine " << x << " " << y << endl;
    string S;
    cin >> S;
    return S == "true";
}

bool qry(int dx, int dy) {
    if (memo[dx].find(dy) != memo[dx].end()) return memo[dx][dy];
    int x = cx + s * dx, y = cy + s * dy;
    if (x <= 0 || x > N || y <= 0 || y > N) return memo[dx][dy] = false;
    return memo[dx][dy] = query(cx + s * dx, cy + s * dy);
}

void solution(int dx, int dy) {
    cout << "solution " << cx + s * dx << " " << cy + s * dy << endl;
}

int main() {
    int x, y, lx = -1, ly = -1, rx = -1;
    cin >> N >> x >> y;

    if (x == 1) lx = 1;
    for (int i = x - 2; i > 0 && lx == -1; i -= 2) {
        if (!query(i, y)) {
            if (query(i + 1, y)) lx = i + 1;
            else lx = i + 2;
        }
    }

    if (x == N) rx = N;
    for (int i = x + 2; i <= N && rx == -1; i += 2) {
        if (!query(i, y)) {
            if (query(i - 1, y)) rx = i - 1;
            else rx = i - 2;
        }
    }

    if (y == 1) ly = 1;
    for (int i = y - 2; i > 0 && ly == -1; i -= 2) {
        if (!query(x, i)) {
            if (query(x, i + 1)) ly = i + 1;
            else ly = i + 2;
        }
    }

    cx = (lx + rx) / 2, cy = ly + cx - lx, s = rx - lx + 1;
    int dx = -1, tx;

    for (;;) {
        if (qry(4, 0)) {dx = 4; break;}
        if (qry(3, 1) || qry(3, -1)) {dx = 3; break;}
        if (qry(2, 0)) {dx = 2; break;}
        if (qry(1, 1) || qry(1, -1)) {dx = 1; break;}
        dx = 0; break;
    }

    if (qry(dx - 2, 4 - dx % 2)) {
        solution(dx - 2, 2 - dx % 2);
    } else if (qry(dx - 2, 2 - dx % 2)) {
        solution(dx - 2, -dx % 2);
    } else {
        solution(dx - 2, -2);
    }
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...