#include <vector>
#include <numeric>
#include <algorithm>
#include <random>
#include <cmath>
#include <set>
// Declare the interactor provided by the judge
long long collisions(std::vector<long long> x);
namespace {
// Helper to find all divisors of val that are strictly greater than limit
std::vector<long long> get_divisors(long long val, long long limit) {
std::vector<long long> divs;
for (long long i = 1; i * i <= val; ++i) {
if (val % i == 0) {
if (i > limit) divs.push_back(i);
if (val / i > limit && val / i != i) divs.push_back(val / i);
}
}
std::sort(divs.begin(), divs.end());
return divs;
}
// Check if a candidate n is correct (Cost: 2)
bool check_n(long long n) {
if (n <= 0) return false;
std::vector<long long> q = {1, n + 1};
return collisions(q) > 0;
}
// Isolate a colliding pair from a set known to have collisions
// Returns the hidden N
int solve_collision(std::vector<long long>& set_with_collision, long long limit_n, std::mt19937_64& rng) {
std::vector<long long> current_set = set_with_collision;
while (true) {
// Optimization: If set is small, brute force all pairs to save queries
if (current_set.size() <= 20) {
for (size_t i = 0; i < current_set.size(); ++i) {
for (size_t j = i + 1; j < current_set.size(); ++j) {
long long diff = std::abs(current_set[i] - current_set[j]);
if (diff == 0) continue;
// We check divisors. If limit_n is set, we can skip very small divisors
// if we are sure they were ruled out, but checking > 1 is always safe.
std::vector<long long> cands = get_divisors(diff, 1);
for (long long cand : cands) {
if (check_n(cand)) return (int)cand;
}
}
}
// If we reach here, the collision was 'lost' (unlikely) or logic error.
// Break to allow caller to handle or retry (though for deterministic Phase 1 this shouldn't happen)
break;
}
int sz = current_set.size();
int mid = sz / 2;
std::vector<long long> left_part(current_set.begin(), current_set.begin() + mid);
std::vector<long long> right_part(current_set.begin() + mid, current_set.end());
if (collisions(left_part) > 0) {
current_set = left_part;
} else if (collisions(right_part) > 0) {
current_set = right_part;
} else {
// Crossing collision. Shuffle and retry split.
std::shuffle(current_set.begin(), current_set.end(), rng);
}
}
return -1;
}
}
int hack() {
std::mt19937_64 rng(1337);
// --- Phase 1: Deterministic Check for Subtasks 1 & 2 (N <= 1,000,000) ---
// Construct Difference Set S = {1..B} U {B, 2B..}
// With B = 1000, we cover differences up to 1,000,000.
// Size ~ 2000. Cost to query: 2000. Cost to isolate: ~4000.
// Total Phase 1 Cost: ~6000 (Very Cheap).
{
const long long B = 1000;
std::vector<long long> diff_set;
diff_set.reserve(2 * B);
for (int i = 1; i <= B; ++i) diff_set.push_back(i);
for (int i = 1; i <= B; ++i) diff_set.push_back(i * B);
std::sort(diff_set.begin(), diff_set.end());
diff_set.erase(std::unique(diff_set.begin(), diff_set.end()), diff_set.end());
if (collisions(diff_set) > 0) {
// Collision found! N <= 1,000,000 (roughly).
// Do NOT use Binary Search (too expensive). Use D&C Isolation.
int res = solve_collision(diff_set, 1, rng);
if (res != -1) return res;
}
}
// --- Phase 2: Randomized Birthday Attack for Subtask 3 (N <= 10^9) ---
// Remaining Budget: ~104,000.
// We use K = 26,000.
// Cost per attempt: ~26k (query) + ~26k (iso) = ~52k.
// We can afford ~2 clean attempts within budget.
// For N=10^9, P(collision) with 26k is ~50%.
// Even if we go over budget slightly on retries, we get high partial score.
int K = 26000;
std::uniform_int_distribution<long long> dist(1, 20000000000LL);
while (true) {
std::vector<long long> current_set;
current_set.reserve(K);
std::set<long long> distinct_check;
while (current_set.size() < K) {
long long val = dist(rng);
if (distinct_check.insert(val).second) {
current_set.push_back(val);
}
}
if (collisions(current_set) > 0) {
int res = solve_collision(current_set, 1, rng);
if (res != -1) return res;
}
}
return -1;
}
