Submission #538500

#	Time	Username	Problem	Language	Result	Execution time	Memory
538500		joshualiu555	Aliens (IOI07_aliens)	C++17	40 / 100	3 ms	312 KiB

aliens

/*
  _____                                     _        _
 / ____|                                   | |      | |
| |  __ _ __ __ _ ___ ___ _   _ _ __   ___ | |_ __ _| |_ ___
| | |_ | '__/ _` / __/ __| | | | '_ \ / _ \| __/ _` | __/ _ \
| |__| | | | (_| \__ \__ \ |_| | |_) | (_) | || (_| | || (_) |
 \_____|_|  \__,_|___/___/\__, | .__/ \___/ \__\__,_|\__\___/
                           __/ | |
                          |___/|_|
*/

#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, 32) {
        if (!query(x0 + (1 << i), y0)) {
            r = x0 + (1 << i);
            break;
        }
    }
    int right = -1;
    while (l <= r) {
        int m = (l + r + 1) / 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;

//    cerr << m << ' ' << left << ' ' << right << ' ' << top << endl;

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

//    cerr << cx << ' ' << cy << endl;

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

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

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

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

//    cerr << lx << ' ' << rx << ' ' << tx << ' ' << bx << endl;
    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 (stderr)

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: 10 / 10
• Subtask 2: 0 / 10
• Subtask 3: 0 / 10
• Subtask 4: 10 / 10
• Subtask 5: 10 / 10
• Subtask 6: 0 / 10
• Subtask 7: 0 / 10
• Subtask 8: 10 / 10
• Subtask 9: 0 / 10
• Subtask 10: 0 / 10