Submission #715540

#	Time	Username	Problem	Language	Result	Execution time	Memory
715540		jophyyjh	Cup of Jamshid (IOI17_cup)	C++14	100 / 100	1 ms	212 KiB

cup

/**
 * 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};
}

• Subtask 1: 100 / 100