oj.uz

답안 #538435

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
538435 2022-03-16T22:38:31 Z joshualiu555 Aliens (IOI07_aliens) C++17
0 / 100
 4 ms 208 KB 
/*
  _____                                     _        _
 / ____|                                   | |      | |
| |  __ _ __ __ _ ___ ___ _   _ _ __   ___ | |_ __ _| |_ ___
| | |_ | '__/ _` / __/ __| | | | '_ \ / _ \| __/ _` | __/ _ \
| |__| | | | (_| \__ \__ \ |_| | |_) | (_) | || (_| | || (_) |
 \_____|_|  \__,_|___/___/\__, | .__/ \___/ \__\__,_|\__\___/
                           __/ | |
                          |___/|_|
*/

#pragma gcc target ("avx2")
#pragma gcc optimization ("O3")
#pragma gcc optimization ("unroll-loops")

#include <bits/stdc++.h>

using namespace std;

#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
template<class T> using segset = tree<T, null_type, less<T>, rb_tree_tag,tree_order_statistics_node_update>;

#define FOR(i, x, n) for (int i = x; i <= n; i++)
#define F0R(i, x, n) for (int i = x; i >= n; i--)
#define TRAV(it, x) for (auto it = x.begin(); it != x.end(); it++)
#define rall(x) x.rbegin(), x.rend()
#define all(x) x.begin(), x.end()
//#define f first
//#define s second
#define sz size
#define pob pop_back
#define pf push_front
#define pb push_back
#define ins insert
#define mp make_pair
#define rz resize
#define asg assign
#define rev reverse
#define lb lower_bound
#define ub upper_bound
// fill for 1
// 0x3f3f3f3f for 1e9
#define mem(a, x) memset(a, x, sizeof(a))
#define HEX 0x3f3f3f3f

using ll = long long;
const int INF = 2e5 + 5;
const int MOD = 1e9 + 7;
// DLRU
const int dx[4] = {1, 0, 0, -1};
const int dy[4] = {0, -1, 1, 0};

int query(int x, int y) {
    cout << "examine" << ' ' << x << ' ' << y << endl;
    string s;
    cin >> s;
    return s == "true";
}

int main()
{
    std::ios_base::sync_with_stdio(false); cin.tie(0);

    int n, x0, y0;
    cin >> n >> x0 >> y0;

    // find right coordinate of initial square
    int l = x0, r = x0;
    FOR(i, 0, 31) {
        if (!query(x0 + (1 << i), y0)) {
            r = x0 + (1 << i);
            break;
        }
    }
    int right = -1;
    while (l <= r) {
        int m = (l + r) / 2;
        if (query(m, y0)) {
            right = m;
            l = m + 1;
        } else {
            r = m - 1;
        }
    }

    // find left coordinate of initial square
    l = x0, r = x0;
    FOR(i, 0, 31) {
        if (!query(x0 - (1 << i), y0)) {
            l = x0 - (1 << i);
            break;
        }
    }
    int left = -1;
    while (l <= r) {
        int m = (l + r) / 2;
        if (query(m, y0)) {
            left = m;
            r = m - 1;
        } else {
            l = m + 1;
        }
    }

    // find top coordinate of initial square
    int t = y0, b = y0;
    FOR(i, 0, 31) {
        if (!query(x0, y0 + (1 << i))) {
            t = y0 + (1 << i);
            break;
        }
    }
    int top = -1;
    while (b <= t) {
        int m = (t + b) / 2;
        if (query(x0, m)) {
            top = m;
            b = m + 1;
        } else {
            t = m - 1;
        }
    }

    int m = right - left + 1;
    int cx = (right + left) / 2, cy = top - m / 2;

    int lx = cx;
    FOR(i, 1, 2) {
        if (query(lx - 2 * m * i, cy)) {
            lx -= 2 * m;
        } else {
            break;
        }
    }

    int rx = cx;
    FOR(i, 1, 2) {
        if (query(lx + 2 * m * i, cy)) {
            lx += 2 * m;
        } else {
            break;
        }
    }

    int tx = cy;
    FOR(i, 1, 2) {
        if (query(cx, cy + 2 * m * i)) {
            tx += 2 * m;
        } else {
            break;
        }
    }

    int bx = cy;
    FOR(i, 1, 2) {
        if (query(cx, cy - 2 * m * i)) {
            bx -= 2 * m;
        } else {
            break;
        }
    }

    cout << "solution " << (lx + rx) / 2 << ' ' << (tx + bx) / 2 << '\n';

    return 0;
}

/*
 * Find M by finding the top, left, and right coordinates
 * of the initial square
 *
 * Since the checkeboards are spaced 2 * M apart,
 * test 2^0, 2^1, 2^x until you find a white cell
 * Then binary search for the black square
 *
 * Find the center of that square
 * Shift left, right, up, and down until you
 * find an empty square to find its bounds
 *
 * Then find the center of those four points
*/

//

Compilation message

aliens.cpp:12: warning: ignoring '#pragma gcc target' [-Wunknown-pragmas]
   12 | #pragma gcc target ("avx2")
      | 
aliens.cpp:13: warning: ignoring '#pragma gcc optimization' [-Wunknown-pragmas]
   13 | #pragma gcc optimization ("O3")
      | 
aliens.cpp:14: warning: ignoring '#pragma gcc optimization' [-Wunknown-pragmas]
   14 | #pragma gcc optimization ("unroll-loops")
      |

Subtask #1
0 / 10.0

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

Subtask #2
0 / 10.0

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

Subtask #3
0 / 10.0

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

Subtask #4
0 / 10.0

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

Subtask #5
0 / 10.0

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

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

Subtask #7
0 / 10.0

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

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

Subtask #9
0 / 10.0

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

Subtask #10
0 / 10.0

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