#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);
}
}
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;
}
}
int hack() {
// --- Phase 1: Efficient check for small N ---
// Cost: 2500
const int SMALL_LIMIT = 2500;
std::vector<long long> small_q(SMALL_LIMIT);
std::iota(small_q.begin(), small_q.end(), 1);
if (collisions(small_q) > 0) {
// Binary search for small N
int low = 2, high = SMALL_LIMIT;
int ans = high;
while (low <= high) {
int mid = low + (high - low) / 2;
std::vector<long long> q(mid);
std::iota(q.begin(), q.end(), 1);
if (collisions(q) > 0) {
ans = mid;
high = mid - 1;
} else {
low = mid + 1;
}
}
return ans - 1;
}
// --- Phase 2: Large N with Optimized Birthday Attack ---
// Use a reduced K to ensure Total Cost < 110,000
// K=22000 => Isolation cost ~4*K = 88,000. Fits budget.
int K = 22000;
std::mt19937_64 rng(1337);
// Range limited to 2*10^10 to ensure fast factorization
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;
// Generate random set
while (current_set.size() < K) {
long long val = dist(rng);
if (distinct_check.insert(val).second) {
current_set.push_back(val);
}
}
// Initial check (Cost: K)
if (collisions(current_set) > 0) {
// Isolation Phase (Divide & Conquer)
while (true) {
// Optimization: If set is small, brute force all pairs
// 12 elements = 66 pairs. Factorizing 66 differences is cheap.
if (current_set.size() <= 12) {
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]);
std::vector<long long> cands = get_divisors(diff, SMALL_LIMIT);
for (long long cand : cands) {
if (check_n(cand)) return (int)cand;
}
}
}
// Fallback: If no divisor worked (rare), break to retry outer loop
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());
// Check Left (Cost: sz/2)
if (collisions(left_part) > 0) {
current_set = left_part;
}
// Check Right (Cost: sz/2)
else if (collisions(right_part) > 0) {
current_set = right_part;
}
// Crossing Collision
else {
// Both 0, but total > 0. Collision is between Left and Right.
// We must shuffle to try a new split.
std::shuffle(current_set.begin(), current_set.end(), rng);
// Note: We do NOT query 'current_set' again here, we know it collides.
// We just loop back and split the shuffled set.
}
}
}
// If initial check failed, we loop again with a new random set.
}
return -1;
}
