/**
* We only have 32 steps, so it's quite clear that we have to determine x,y bit
* by bit. The process of finding this solution was through trial-and-error, so
* I'll list some important observations and directly describe my sol.
* 1. As the result of each query is |x-x'|^|y-y'|, when we've determined the
* hidden x' and we used a large (?!) enough y, y' can be immediately found
* since xor's inverse is itself.
* 2. Write a value t in binary. |t - 2^d| and |t| differ only at the (d+1)-th
* least significant bit iff that bit of t is 1. (Well, at least this is
* true for t > 2^d. Take t=0 as a counter-example: our claim is false.)
*
* 2. yields a good way to determine x' bit by bit. Here's the full solution:
* (0) Let B = 5 * 10^8, pow be the unique power of 2 between B and 2B.
* (1) Determine the sign of x', ask (pow,0): |y'| has at most 29 bits, while
* |B-x'| has its 30-th least sgn bit 1 iff x <= 0.
* (2) We try to ask (~(-pow), whatever): 2. is best used when we know the
* num of bits in |x-x'|. WLOG let x' be positive. Each time, we can ask
* (-pow + 2^d, whatever) and compare it with the ans of (-pow, whatever).
* The clever trick here is that |x-x'| always has exactly 30 bits. In
* other words, (2) takes 30 steps.
*
* Queries Needed: 31 (Bound not tight)
* Implementation 1 (Full solution, binary)
*/
#include <bits/stdc++.h>
#include "cup.h"
typedef std::vector<int> vec;
const int B = 5e8, B2 = 1e9;
const int two_pow = 1 << 29;
const int MIN_DIGITS = 29;
vec find_cup() {
int sign = ((ask_shahrasb(two_pow, 0) & two_pow) ? -1 : 1);
int initial = ask_shahrasb(-sign * two_pow, B2);
int x = 0;
for (int _ = 0, d = 1; _ < MIN_DIGITS; _++, d <<= 1) {
if ((ask_shahrasb(-sign * (two_pow - d), B2) ^ initial) == d)
x |= d;
}
x *= sign;
int y = B2 - (initial ^ std::abs(x + sign * two_pow));
assert(std::abs(x) <= B && std::abs(y) <= B);
return {x, y};
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
212 KB |
Output is correct |
