Submission #697190

#	Time	Username	Problem	Language	Result	Execution time	Memory
697190		ThegeekKnight16	Aliens (IOI07_aliens)	C++17	100 / 100	3 ms	208 KiB

aliens

#include <bits/stdc++.h>
using namespace std;
int N;
int cnt = 0;
#define int long long

bool query(int x, int y)
{
    if (x < 1 || x > N) return false;
    if (y < 1 || y > N) return false;
    cnt++;
    assert(cnt <= 300);
    cout << "examine " << x << " " << y << endl;
    string resp;
    cin >> resp;
    return (resp == "true");
}

int32_t main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int X0, Y0;
    cin >> N >> X0 >> Y0;


    int Xdir = X0, Xesq = X0;
    for (int k = 30; k >= 0; k--)
    {
        assert(cnt <= 300);
        if (!query(Xdir + (1 << k), Y0)) continue;
        if (k > 0 && !query(Xdir + (1 << (k-1)), Y0)) {k--; continue;}
        if (k > 1 && !query(Xdir + (1 << (k-2)), Y0)) {k -= 2; continue;}
        Xdir += (1 << k);
    }
    assert(cnt <= 300);
    // cerr << "Xdir = " << Xdir << endl;
    for (int k = 30; k >= 0; k--)
    {
        assert(cnt <= 300);
        if (!query(Xesq - (1 << k), Y0)) continue;
        if (k > 0 && !query(Xesq - (1 << (k-1)), Y0)) {k--; continue;}
        if (k > 1 && !query(Xesq - (1 << (k-2)), Y0)) {k -= 2; continue;}
        Xesq -= (1 << k);
    }
    assert(cnt <= 300);
    // cerr << "Xesq = " << Xesq << endl;

    int Ydir = Y0, Yesq = Y0;
    for (int k = 30; k >= 0; k--)
    {
        assert(cnt <= 300);
        if (!query(X0, Ydir + (1 << k))) continue;
        if (k > 0 && !query(X0, Ydir + (1 << (k - 1)))) {k--; continue;}
        if (k > 1 && !query(X0, Ydir + (1 << (k - 2)))) {k -= 2; continue;}
        Ydir += (1 << k);
    }
    assert(cnt <= 300);
    // cerr << "Ydir = " << Ydir << endl;
    for (int k = 30; k >= 0; k--)
    {
        assert(cnt <= 300);
        if (!query(X0, Yesq - (1 << k))) continue;
        if (k > 1 && !query(X0, Yesq - (1 << (k - 2)))) {k -= 2; continue;}
        if (k > 0 && !query(X0, Yesq - (1 << (k - 1)))) {k--; continue;}
        Yesq -= (1 << k);
    }
    assert(cnt <= 300);
    // cerr << "Yesq = " << Yesq << endl;

    int X = (Xesq + Xdir + 1) / 2;
    int Y = (Yesq + Ydir + 1) / 2;
    int M = (Xdir - Xesq + 1);
    // cerr << X << " " << Y << " " << M << endl;
    // cerr << "found M: " << M << endl;
    int Xresp = X; int Yresp = Y;

    if (query(X + (4*M), Y)) Xresp += (2 * M);
    else if (query(X - (4*M), Y)) Xresp -= (2 * M);
    else
    {
        bool b1 = query(X - (2*M), Y);
        bool b2 = query(X + (2*M), Y);
        if (b1 && !b2) Xresp -= M;
        else if (!b1 && b2) Xresp += M;
    }

    assert(cnt <= 300);

    if (query(X, Y + (4*M))) Yresp += (2*M);
    else if (query(X, Y - (4*M))) Yresp -= (2*M);
    else
    {
        bool b1 = query(X, Y - (2*M));
        bool b2 = query(X, Y + (2*M));
        if (b1 && !b2) Yresp -= M;
        else if (!b1 && b2) Yresp += M;
    }
    assert(cnt <= 300);

    cout << "solution " << Xresp << " " << Yresp << 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