oj.uz

Submission #684917

# Submission time Handle Problem Language Result Execution time Memory
684917 2023-01-22T20:29:36 Z finn__ Aliens (IOI07_aliens) C++17
100 / 100
 2 ms 220 KB 
#include <bits/stdc++.h>
using namespace std;

struct point
{
    int64_t x, y;
};

bool is_flattened(point const &p)
{
    cout << "examine " << p.x << ' ' << p.y << endl;
    string s;
    cin >> s;
    return s == "true";
}

point find_border(int64_t n, point const &p, int64_t dx, int64_t dy)
{
    int64_t z0 = 0;
    for (int64_t z = 1; 1 <= p.x + z * dx && p.x + z * dx <= n &&
                        1 <= p.y + z * dy && p.y + z * dy <= n;
         z <<= 1)
    {
        if (!is_flattened({p.x + z * dx, p.y + z * dy}))
            break;
        z0 = 2 * z;
    }

    int64_t a = z0 / 2, b = z0;
    while (a < b)
    {
        int64_t z = (a + b + 1) / 2;
        if (1 <= p.x + z * dx && p.x + z * dx <= n &&
            1 <= p.y + z * dy && p.y + z * dy <= n &&
            is_flattened({p.x + z * dx, p.y + z * dy}))
            a = z;
        else
            b = z - 1;
    }
    return {p.x + a * dx, p.y + a * dy};
}

int main()
{
    int64_t n;
    point p0;
    cin >> n >> p0.x >> p0.y;

    point left = find_border(n, p0, -1, 0),
          right = find_border(n, p0, 1, 0),
          top = find_border(n, p0, 0, -1);

    int64_t const m = right.x - left.x + 1;

    int64_t left_squares = 0, right_squares = 0, top_squares = 0;
    while (p0.x - (left_squares + 1) * 2 * m >= 1 &&
           is_flattened({p0.x - (left_squares + 1) * 2 * m, p0.y}))
        left_squares++;
    while (p0.x + (right_squares + 1) * 2 * m <= n &&
           is_flattened({p0.x + (right_squares + 1) * 2 * m, p0.y}))
        right_squares++;
    while (p0.y - (top_squares + 1) * 2 * m >= 1 &&
           is_flattened({p0.x, p0.y - (top_squares + 1) * 2 * m}))
        top_squares++;

    point center;
    if (left_squares + right_squares == 2)
        center = {left.x + (1 - left_squares) * 2 * m + m / 2,
                  top.y + (1 - top_squares) * 2 * m + m / 2};
    else
        center = {left.x - left_squares * 2 * m + m + m / 2,
                  top.y - top_squares * 2 * m + m + m / 2};

    cout << "solution " << center.x << ' ' << center.y << endl;
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 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 0 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 0 ms 208 KB Output is correct
2 Correct 1 ms 220 KB Output is correct

Subtask #4
10.0 / 10.0

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

Subtask #5
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 #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 1 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 1 ms 208 KB Output is correct
2 Correct 1 ms 208 KB Output is correct
3 Correct 1 ms 208 KB Output is correct

Subtask #9
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 #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 1 ms 208 KB Output is correct