Submission #525602

#	Time	Username	Problem	Language	Result	Execution time	Memory
525602		tabr	Cup of Jamshid (IOI17_cup)	C++17	100 / 100	1 ms	204 KiB

cup

#include <bits/stdc++.h>
using namespace std;
#ifdef tabr
#include "library/debug.cpp"
#else
#define debug(...)
#endif

#ifdef tabr
function<int(int, int)> ask_shahrasb;
#else
#include "cup.h"
#endif

vector<int> find_cup() {
    int x = (int) -5e8;
    int y = (int) -5e8;
    int z = ask_shahrasb(x, y);
    // [0, 1 << (i + 1)) -> [0, 1 << i)
    int v = ask_shahrasb(x, y + (1 << 29) - 1);
    if (z & (1 << 29)) {
        if (v & (1 << 29)) {
            x += 1 << 29;
        } else {
            y += 1 << 29;
        }
    } else {
        if (v & (1 << 29)) {
            x += 1 << 29;
            y += 1 << 29;
        }
    }
    for (int i = 28; i >= 0; i--) {
        int w = ask_shahrasb(x - (1 << i), y);
        if (z & (1 << i)) {
            if (w & (1 << (i + 1))) {
                x += 1 << i;
            } else {
                y += 1 << i;
            }
        } else {
            if (w & (1 << (i + 1))) {
                x += 1 << i;
                y += 1 << i;
            }
        }
    }
    return {x, y};
}

mt19937 rng((unsigned int) chrono::steady_clock::now().time_since_epoch().count());

int rand_int(int a, int b) {  // [a, b]
    return uniform_int_distribution<int>(a, b)(rng);
}

#ifdef tabr
int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    int tt = 10;
    while (tt--) {
        int a = rand_int((int) -5e8, (int) 5e8);
        int b = rand_int((int) -5e8, (int) 5e8);
        int cnt = 0;
        ask_shahrasb = [&](int x, int y) {
            cnt++;
            assert(max(abs(x), abs(y)) <= (int) 1e9);
            return abs(a - x) ^ abs(b - y);
        };
        auto c = find_cup();
        debug(c, a, b, cnt);
        assert(c[0] == a && c[1] == b);
    }
    return 0;
}
#endif

• Subtask 1: 100 / 100