oj.uz

Submission #543816

# Submission time Handle Problem Language Result Execution time Memory
543816 2022-03-31T12:42:08 Z timreizin Aliens (IOI07_aliens) C++17
100 / 100
 3 ms 208 KB 
#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.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 208 KB Output is correct
2 Correct 1 ms 208 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 208 KB Output is correct
2 Correct 1 ms 208 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 208 KB Output is correct
2 Correct 1 ms 208 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 208 KB Output is correct
2 Correct 2 ms 208 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 208 KB Output is correct
2 Correct 1 ms 208 KB Output is correct

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 208 KB Output is correct
2 Correct 1 ms 208 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 208 KB Output is correct
2 Correct 2 ms 208 KB Output is correct
3 Correct 1 ms 208 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 208 KB Output is correct
2 Correct 1 ms 208 KB Output is correct
3 Correct 2 ms 208 KB Output is correct

Subtask #9
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 208 KB Output is correct
2 Correct 2 ms 208 KB Output is correct
3 Correct 1 ms 208 KB Output is correct

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 208 KB Output is correct
2 Correct 1 ms 208 KB Output is correct
3 Correct 2 ms 208 KB Output is correct