제출 #484803

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
484803		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;
    }

    bool val = Question(ans.first, ans.second);
    while (Question(ans.first, ans.second-M) != val) {
        ans.second -= M;
        val = Question(ans.first, ans.second);
    }
    ans.second += M;

    val = Question(ans.first, ans.second);
    while (Question(ans.first-M, ans.second) != val) {
        ans.first -= M;
        val = Question(ans.first, ans.second);
    }
    ans.first += M;

    return ans;
}

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