#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
std::vector<long long> get_divisors(long long val) {
std::vector<long long> divs;
for (long long i = 1; i * i <= val; ++i) {
if (val % i == 0) {
divs.push_back(i);
if (val / i != i) divs.push_back(val / i);
}
}
std::sort(divs.begin(), divs.end());
return divs;
}
// Verify if 'n' is the hidden number (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;
}
// Efficiently isolate a collision from a set known to contain one
int isolate_collision(std::vector<long long>& current_set, std::mt19937_64& rng) {
while (true) {
// Optimization: If set is small, brute force all pair differences
// This saves recursion queries at the bottom of the tree
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;
std::vector<long long> cands = get_divisors(diff);
for (long long cand : cands) {
// Optimization: We can skip very small candidates
// if we handled them in previous phases, but checking > 1 is safe.
if (cand > 1 && check_n(cand)) return (int)cand;
}
}
}
break; // Should not happen if collision exists
}
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());
// Check Left
if (collisions(left_part) > 0) {
current_set = left_part;
}
// Check Right
else if (collisions(right_part) > 0) {
current_set = right_part;
}
// Crossing Collision (One in Left, One in Right)
else {
// Shuffle to try a new split
std::shuffle(current_set.begin(), current_set.end(), rng);
}
}
return -1;
}
}
int hack() {
std::mt19937_64 rng(1337);
// --- Phase 1: Small N Binary Search Base (Linear Probe) ---
// Efficiently handles N <= 2500
// Cost: 2500
{
const int SMALL_LIMIT = 2500;
std::vector<long long> q(SMALL_LIMIT);
std::iota(q.begin(), q.end(), 1);
if (collisions(q) > 0) {
// Standard Binary Search for N in range [1, 2500]
int low = 2, high = SMALL_LIMIT;
int ans = high;
while (low <= high) {
int mid = low + (high - low) / 2;
std::vector<long long> test_q(mid);
std::iota(test_q.begin(), test_q.end(), 1);
if (collisions(test_q) > 0) {
ans = mid;
high = mid - 1;
} else {
low = mid + 1;
}
}
return ans - 1;
}
}
// --- Phase 2: Medium N (<= 1,000,000) Deterministic Check ---
// Uses Difference Set Construction.
// Set Size: ~2000. Cost: 2000.
{
const long long B = 1000; // sqrt(1,000,000)
std::vector<long long> diff_set;
diff_set.reserve(2 * B);
for (long long i = 1; i <= B; ++i) diff_set.push_back(i);
for (long long i = 1; i <= B; ++i) diff_set.push_back(i * B);
// Cleanup
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 confirmed for N <= 1,000,000.
// Isolate it using Divide & Conquer (Cost ~4000)
return isolate_collision(diff_set, rng);
}
}
// --- Phase 3: Large N (<= 10^9) Randomized Strategy ---
// We use a small K to keep total cost low (< 110,000).
// K = 22,000.
// Cost Analysis:
// Phase 1 (2.5k) + Phase 2 (2k) + Phase 3 Probe (22k) + Isolation (44k)
// Total ~ 70.5k. This fits SAFELY in the 110k budget.
// If we fail the first random try, we loop. The score penalty for cost is log-based,
// so it's better to retry than to fail.
int K = 22000;
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) {
return isolate_collision(current_set, rng);
}
// Loop continues if no collision found (unlucky case)
}
return -1;
}
