oj.uz

Submission #543804

# Submission time Handle Problem Language Result Execution time Memory
543804 2022-03-31T12:12:48 Z timreizin Aliens (IOI07_aliens) C++17
0 / 100
 2 ms 464 KB 
#include <iostream>
#include <vector>
#include <array>
#include <numeric>
#include <cassert>
#include <tuple>

using namespace std;

using ll = long long;

int N;
int table[100][100];

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};
        }
    }
    assert(false);
    return {-1, -1, -1};
}

void fillsqr(int x, int y, int m)
{
    for (int i = x; i < x + m; ++i)
    {
        for (int j = y; j < y + m; ++j)
        {
            table[i][j] = 1;
        }
    }
}

int main()
{
    /*fillsqr(5, 2, 3);
    fillsqr(11, 2, 3);
    fillsqr(17, 2, 3);
    fillsqr(5, 8, 3);
    fillsqr(11, 8, 3);
    fillsqr(17, 8, 3);
    fillsqr(5, 14, 3);
    fillsqr(11, 14, 3);
    fillsqr(17, 14, 3);
    fillsqr(8, 5, 3);
    fillsqr(14, 5, 3);
    fillsqr(8, 11, 3);
    fillsqr(14, 11, 3);*/
    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;
    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 - m)) y -= m;
    x += 2 * m + m / 2;
    y += 2 * m + m / 2;
    cout << "solution " << x << ' ' << y << '\n';
    return 0;
}

/*
 false
 true *3
 false *3
 */

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 208 KB Incorrect
2 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

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

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 1 ms 464 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 208 KB Incorrect
2 Halted 0 ms 0 KB -

Subtask #5
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 208 KB Incorrect
2 Halted 0 ms 0 KB -

Subtask #6
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 208 KB Incorrect
2 Halted 0 ms 0 KB -

Subtask #7
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 208 KB Incorrect
2 Halted 0 ms 0 KB -

Subtask #8
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 208 KB Incorrect
2 Halted 0 ms 0 KB -

Subtask #9
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 1 ms 464 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #10
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 208 KB Incorrect
2 Halted 0 ms 0 KB -