#include "hack.h"
#include <vector>
#include <numeric>
#include <algorithm>
#include <cmath>
#include <random>
// Declare the interactor function provided by the grading system
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;
}
}
int hack() {
// Constants tuned for the 110,000 cost limit and 10^9 range
const long long SMALL_LIMIT = 2000;
const long long STRIDE = 21379; // A large prime number
const int K = 48000; // K * STRIDE > 10^9, fits within budget
// --- Phase 1: Eliminate small n ---
// Query {1, 2, ..., 2000}
std::vector<long long> small_query(SMALL_LIMIT);
std::iota(small_query.begin(), small_query.end(), 1);
if (collisions(small_query) > 0) {
// If collisions exist, n < 2000. Binary search for the smallest size
// that causes a collision.
int low = 2, high = SMALL_LIMIT;
int ans = 2;
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;
}
}
// If {1..ans} has a collision but {1..ans-1} doesn't,
// then 'ans' collided with '1' (or similar), implying n = ans - 1.
return ans - 1;
}
// --- Phase 2: Solve for large n ---
// Construct a stride-based query vector
std::vector<long long> large_query;
large_query.reserve(K);
for (int i = 1; i <= K; ++i) {
large_query.push_back(i * STRIDE);
}
// Randomized Divide & Conquer to isolate a colliding pair
std::mt19937 rng(1337);
std::shuffle(large_query.begin(), large_query.end(), rng);
std::vector<long long> current_set = large_query;
// Narrow down to a pair
while (current_set.size() > 2) {
int n_size = current_set.size();
int mid = n_size / 2;
// Split set into Left and Right
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());
// Greedily recurse into a half that contains collisions
if (collisions(left_part) > 0) {
current_set = left_part;
continue;
}
if (collisions(right_part) > 0) {
current_set = right_part;
continue;
}
// If neither half has collisions, but the parent set did, the collisions
// are "crossing" (one element in Left, one in Right).
// Reshuffle the parent set to attempt a different split.
std::shuffle(current_set.begin(), current_set.end(), rng);
}
// We now have a small set (size 2) containing a collision
long long val1 = current_set[0];
long long val2 = current_set[1];
long long diff = std::abs(val1 - val2);
// n must be a divisor of this difference
std::vector<long long> candidates = get_divisors(diff, SMALL_LIMIT);
for (long long cand : candidates) {
// Verify the candidate.
// If n = cand, then 1 and cand+1 will map to the same bucket (1 mod n).
// Since we iterate from smallest divisor, the first valid one is n.
std::vector<long long> verify_q = {1, cand + 1};
if (collisions(verify_q) > 0) {
return (int)cand;
}
}
return -1; // Should not be reached
}
