oj.uz

답안 #684907

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
684907 2023-01-22T20:05:58 Z finn__ Aliens (IOI07_aliens) C++17
60 / 100
 2 ms 464 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;
    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

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.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 208 KB Output is correct
2 Correct 0 ms 208 KB Output is correct

Subtask #2
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 0 ms 208 KB Incorrect
2 Halted 0 ms 0 KB -

Subtask #3
10.0 / 10.0

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 208 KB Output is correct
2 Correct 1 ms 208 KB Output is correct

Subtask #5
10.0 / 10.0

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 208 KB Output is correct
2 Correct 1 ms 208 KB Output is correct

Subtask #7
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 208 KB Output is correct
2 Correct 1 ms 208 KB Output is correct
3 Runtime error 1 ms 336 KB Execution killed with signal 6
4 Halted 0 ms 0 KB -

Subtask #8
10.0 / 10.0

# 결과 실행 시간 메모리 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 #9
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 2 ms 464 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #10
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 208 KB Output is correct
2 Incorrect 2 ms 208 KB Incorrect
3 Halted 0 ms 0 KB -