#include "cup.h"
#include <vector>
using namespace std;
typedef long long ll;
// Constants for the coordinate boundaries
const ll MAX_COORD = 5e8;
const ll SHIFT_X = -2 * MAX_COORD; // -1,000,000,000
const ll SHIFT_Y = -MAX_COORD; // -500,000,000
/**
* Helper to check if the higher bits (above bit 'k')
* remain the same between two XOR results.
*/
bool higher_bits_match(ll val1, ll val2, int k) {
// Create a mask that ignores the k-th bit and lower bits
// 1LL << 33 covers the range needed for 10^9
ll mask = ((1LL << 33) - 1) - ((1LL << k));
return (val1 & mask) == (val2 & mask);
}
vector<int> find_cup() {
// 1. Get the baseline XOR sum at our shifted origin
// Let DX = |x_cup - SHIFT_X| and DY = |y_cup - SHIFT_Y|
// baseline_xor = DX ^ DY
ll baseline_xor = ask_shahrasb(SHIFT_X, SHIFT_Y);
ll recovered_dx = 0;
ll recovered_dy = 0;
// 2. Determine DX and DY bit by bit (0 to 30)
for (int i = 0; i < 31; i++) {
ll bit_value = (1LL << i);
// Query the distance again, but shift the query x by 2^i
// new_xor = |x_cup - (SHIFT_X + 2^i)| ^ |y_cup - SHIFT_Y|
ll new_xor = ask_shahrasb(SHIFT_X + bit_value, SHIFT_Y);
// If the higher bits of the XOR result didn't change wildly,
// it means subtracting 2^i from the distance didn't cause a "borrow"
// from the higher bits. This tells us if the i-th bit of DX was 1 or 0.
if (higher_bits_match(baseline_xor, new_xor, i)) {
// Calculate what the i-th bit of DY must be based on the XOR sum
recovered_dy += bit_value ^ (baseline_xor & bit_value);
} else {
// Otherwise, the bit in DX was 0, so we take the bit from the XOR sum
recovered_dy += (baseline_xor & bit_value);
}
}
// 3. Use the XOR property: If DX ^ DY = baseline, then DX = baseline ^ DY
recovered_dx = baseline_xor ^ recovered_dy;
// 4. Handle potential edge case where DX might be slightly off
// due to the bitwise reconstruction logic.
if (SHIFT_X + recovered_dx > MAX_COORD) {
// Find the highest power of 2 in recovered_dx and subtract it
ll highest_bit = 0;
for (int i = 33; i >= 0; i--) {
if ((recovered_dx >> i) & 1) {
highest_bit = (1LL << i);
break;
}
}
recovered_dx -= highest_bit;
}
// 5. Translate back from shifted distances to actual coordinates
int final_x = (int)(SHIFT_X + recovered_dx);
int final_y = (int)(SHIFT_Y + recovered_dy);
return {final_x, final_y};
}
