#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
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
204 KB |
Output is correct |
