#include <iostream>
#include <fstream>
#include <algorithm>
#include <cstring>
#include <climits>
#include <cassert>
#include <tuple>
#include <queue>
#include <stack>
#include <vector>
#include <map>
#include <set>
#include <string>
#include <unordered_set>
#include <unordered_map>
using namespace std;
typedef long long LL;
typedef vector<int> Vi;
typedef vector<LL> VL;
typedef vector<bool> Vb;
typedef vector<vector<int>> Vii;
#define forR(i, n) for (int i = 0; i < (n); i++)
int ask_shahrasb(int x, int y);
#define bit1(x, a) (((x) & (1 << (a))) > 0)
Vi find_cup() {
int x0 = -(1 << 29), y0 = -(1 << 29);
int xl = 30, yl = 30;
// [x0, x0 + 2^xl)
while (xl + yl > 0) {
if (xl == yl && xl < 30) {
xl--; yl--;
int xq = x0 - (1 << xl);
int r = ask_shahrasb(xq, y0);
int r_2 = r >> xl;
assert(r_2 < 4);
int len = 1 << xl;
switch (r_2) {
case 0b11: x0 += len; y0 += len; break;
case 0b10: x0 += len; break;
case 0b01: break;
case 0b00: y0 += len; break;
}
} else if (yl > xl) {
// dec yl
int r = ask_shahrasb(x0, y0);
yl--;
if (bit1(r, yl)) {
y0 += 1 << yl;
}
} else {
// dec xl
xl--;
int r = ask_shahrasb(x0, y0 + (1 << xl));
if (bit1(r, xl)) {
x0 += 1 << xl;
}
}
}
return Vi{ x0, y0 };
}
#ifdef TEST_LOCAL
int cnt = 0;
int ax = -123897, ay = 378732719;
int ask_shahrasb(int x, int y) {
cnt++;
assert(abs(x) <= (int)1e9 && abs(y) <= (int)1e9);
return abs(x - ax) ^ abs(y - ay);
}
int main() {
auto r = find_cup();
assert(r[0] == ax && r[1] == ay);
return 0;
}
#endif
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
332 KB |
Output is correct |
