Submission #543816

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

aliens

#include <iostream>
#include <vector>
#include <array>
#include <numeric>
#include <cassert>
#include <tuple>

using namespace std;

using ll = long long;

#define int long long

int N;

bool ask(int x, int y)
{
    if (x < 1 || y < 1 || y > N || x > N) return false;
    cout << "examine " << x << ' ' << y << '\n';
    cout.flush();
    string res;
    cin >> res;
    return res == "true";
}

tuple<int, int, int> find(int xl, int xr, int y0)
{
    for (int i = 0; i < 3; ++i)
    {
        for (int j = i; j < 3; ++j)
        {
            if ((xr - xl + 1) % ((j - i) * 2 + 1) != 0) continue;
            int m = (xr - xl + 1) / ((j - i) * 2 + 1);
            int e = xl - (2 * i * m);
            bool flag = true;
            for (int k = 0; k < 3; ++k)
            {
                flag &= ask(e + k * 2 * m, y0);
                flag &= !ask(e + k * 2 * m - 1, y0);
                flag &= !ask(e + (k * 2 + 1) * m, y0);
                flag &= ask(e + (k * 2 + 1) * m - 1, y0);
            }
            if (flag) return {e, m, 0};
        }
    }
    for (int i = 0; i < 2; ++i)
    {
        for (int j = 0; j < 2; ++j)
        {
            if ((xr - xl + 1) % ((j - i) * 2 + 1) != 0) continue;
            int m = (xr - xl + 1) / ((j - i) * 2 + 1);
            int e = xl - (2 * i * m);
            bool flag = true;
            for (int k = 0; k < 2; ++k)
            {
                flag &= ask(e + k * 2 * m, y0);
                flag &= !ask(e + k * 2 * m - 1, y0);
                flag &= !ask(e + (k * 2 + 1) * m, y0);
                flag &= ask(e + (k * 2 + 1) * m - 1, y0);
            }
            if (flag) return {e, m, 1};
        }
    }
    return {-1, -1, -1};
}

signed main()
{
    cin.tie(0)->sync_with_stdio(0);
    int n, x0, y0;
    cin >> n >> x0 >> y0;
    N = n;
    int l = 1, r = x0;
    while (l < r)
    {
        int m = (l + r) >> 1;
        if (ask(m, y0)) r = m;
        else l = m + 1;
    }
    int xl = l;
    l = x0;
    r = n + 1;
    while (l < r)
    {
        int m = (l + r) >> 1;
        if (ask(m, y0)) l = m + 1;
        else r = m;
    }
    int xr = l - 1;
    auto [x, m, t] = find(xl, xr, y0);
    if (t)
    {
        x -= m;
        y0 -= m;
    }
    l = y0;
    r = y0 + m;
    while (l < r)
    {
        int m = (l + r) >> 1;
        if (ask(x, m)) l = m + 1;
        else r = m;
    }
    int y = l - 1;
    y -= m - 1;
    while (ask(x, y - 2 * m)) y -= 2 * m;
    x += 2 * m + m / 2;
    y += 2 * m + m / 2;
    cout << "solution " << x << ' ' << y << '\n';
    return 0;
}

• 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