제출 #484829

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
484829		Alexandruabcde	Aliens (IOI07_aliens)	C++14	0 / 100	2 ms	200 KiB

aliens

#include <bits/stdc++.h>

using namespace std;

typedef long long LL;

LL N, X0, Y0;

bool Question (LL X, LL Y) {
    if (X < 1 || X > N || Y < 1 || Y > N) return 0;

    cout << "examine " << X << " " << Y << '\n';
    string ans;

    cin >> ans;

    if (ans == "true") return 1;

    return 0;
}

LL FindM (LL X0, LL Y0) {
    LL putere = 1;

    for (; Question(X0, Y0+putere); putere<<=1);

    LL st = Y0, dr = Y0 + putere;
    LL Y_Up = Y0;

    while (st <= dr) {
        LL mij = (st + dr) / 2;
        bool val = Question(X0, mij);
        if (val) {
            Y_Up = mij;
            st = mij + 1;
        }
        else dr = mij - 1;
    }

    putere = 1;
    for (; Question(X0, Y0-putere); putere<<=1);

    st = Y0-putere, dr = Y0;
    LL Y_Down = Y0;

    while (st <= dr) {
        LL mij = (st + dr) / 2;
        bool val = Question(X0, mij);
        if (val) {
            Y_Down = mij;
            dr = mij - 1;
        }
        else st = mij + 1;
    }

    return Y_Up - Y_Down + 1;
}

pair <LL, LL> FindCorner (LL M, LL X0, LL Y0) {
    pair <LL, LL> ans;

    LL putere = 1;
    for (; Question(X0, Y0-putere); putere<<=1);
    LL st = Y0-putere, dr = Y0;
    while (st <= dr) {
        LL mij = (st + dr) / 2;
        bool val = Question(X0, mij);
        if (val) {
            ans.second = mij;
            dr = mij - 1;
        }
        else st = mij + 1;
    }

    putere = 1;
    for (; Question(X0-putere, Y0); putere<<=1);
    st = X0-putere, dr = X0;
    while (st <= dr) {
        LL mij = (st + dr) / 2;
        bool val = Question(mij, Y0);
        if (val) {
            ans.first = mij;
            dr = mij - 1;
        }
        else st = mij + 1;
    }

    pair <LL, LL> sol = ans;
    for (int i = -4; i <= 4; ++ i )
        for (int j = -4; j <= 4; ++ j ) {
            pair <LL, LL> aux = {ans.first + i * M, ans.second + j * M};

            bool val = Question(aux.first, aux.second);

            if (!val) continue;

            if (aux.first < sol.first) sol = aux;
            else if (aux.first == sol.first && aux.second < sol.second) sol = aux;
        }

    return sol;
}

int main () {
    cin >> N >> X0 >> Y0;

    LL M = FindM(X0, Y0);
    pair <LL, LL> Corner = FindCorner(M, X0, Y0);

    int M_int = (int)M;
    pair <int, int> Corner_int = Corner;

    cout << "solution " << Corner_int.first + 2 * M_int + 1 << " " << Corner_int.second + 2 * M_int + 1 << '\n';
    return 0;
}

• Subtask 1: 0 / 10
• Subtask 2: 0 / 10
• Subtask 3: 0 / 10
• Subtask 4: 0 / 10
• Subtask 5: 0 / 10
• Subtask 6: 0 / 10
• Subtask 7: 0 / 10
• Subtask 8: 0 / 10
• Subtask 9: 0 / 10
• Subtask 10: 0 / 10