#include "cup.h"
#include <vector>
using namespace std;
/**
* The goal is to find (target_x, target_y).
* We know the result of ask_shahrasb(qx, qy) is:
* (abs(qx - target_x)) XOR (abs(qy - target_y))
*/
vector<int> find_cup() {
// 1. Pick a reference point at the maximum possible boundary.
// This ensures (reference - target) is always a positive distance.
const int REF = 500000000;
// Get the XOR sum of the total horizontal and vertical distances.
int total_xor_dist = ask_shahrasb(REF, REF);
// These will store the distances from our REF point to the cup.
int dist_x = 0;
int dist_y = 0;
// 2. Determine each bit of the distances (from 2^29 down to 2^0).
for (int i = 29; i >= 0; i--) {
int bit_value = (1 << i);
// Query the point shifted by the current bit power.
// We shift the X query point to see how it affects the total XOR.
int new_xor = ask_shahrasb(REF - bit_value, REF);
// Logic: How did the XOR change when we subtracted bit_value from X?
// We use the property: (A ^ B) ^ ( (A-bit) ^ B ) to isolate the bit's behavior.
bool bit_in_x_dist = false;
if (total_xor_dist & bit_value) {
// Case A: The bit is present in (dist_x XOR dist_y).
// This means the bit is set in either X or Y, but NOT both.
if ((new_xor ^ total_xor_dist) != bit_value) {
bit_in_x_dist = true;
}
} else {
// Case B: The bit is NOT present in (dist_x XOR dist_y).
// This means the bit is either 0 in both, or 1 in both.
if ((new_xor ^ total_xor_dist) != bit_value) {
// If the XOR changed unexpectedly, the bit must be 1 in both.
bit_in_x_dist = true;
dist_y |= bit_value; // Set bit in Y as well
}
}
if (bit_in_x_dist) {
dist_x |= bit_value;
}
}
// 3. Convert distances back to coordinates.
// Distance = REF - Target => Target = REF - Distance
int target_x = REF - dist_x;
int target_y = REF - dist_y;
return {target_x, target_y};
}
