Submission #684907

#	Time	Username	Problem	Language	Result	Execution time	Memory
684907		finn__	Aliens (IOI07_aliens)	C++17	60 / 100	2 ms	464 KiB

aliens

#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;
    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)
    {
        z0 = z;
        if (!is_flattened({p.x + z * dx, p.y + z * dy}))
            break;
    }

    if (p.x + z0 * dx < 1)
        z0 = p.x - 1;
    if (p.y + z0 * dy < 1)
        z0 = p.y - 1;
    if (p.x + z0 * dx > n)
        z0 = n - p.x;
    if (p.y + z0 * dy > n)
        z0 = n - p.y;

    int64_t a = z0 / 2, b = z0 - 1;
    while (a < b)
    {
        int64_t z = (a + b + 1) / 2;
        if (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;
    assert(m & 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;
}

Compilation message (stderr)

aliens.cpp: In function 'point find_border(int64_t, const point&, int64_t, int64_t)':
aliens.cpp:29:18: warning: 'z0' may be used uninitialized in this function [-Wmaybe-uninitialized]
   29 |     if (p.x + z0 * dx < 1)
      |               ~~~^~~~

• Subtask 1: 10 / 10
• Subtask 2: 0 / 10
• Subtask 3: 10 / 10
• Subtask 4: 10 / 10
• Subtask 5: 10 / 10
• Subtask 6: 10 / 10
• Subtask 7: 0 / 10
• Subtask 8: 10 / 10
• Subtask 9: 0 / 10
• Subtask 10: 0 / 10