#include <iostream>
#include <vector>
#include <random>
#include <algorithm>
//#define nONLINE_JUDGE
using namespace std;
// The interactor function provided by the grader
long long collisions(std::vector<long long> x);
// Global arrays for fast memory access, reused across hack() calls
int count_arr[1000005];
int hack() {
int M = 3000000;
int K1 = 12000;
int K_new = 10000;
// Static random number generator to continue sequence across calls
static mt19937 rng(1337);
vector<long long> X;
static vector<bool> used(3000005, false);
// Generate the first random set
while (X.size() < K1) {
long long x = uniform_int_distribution<long long>(1, M)(rng);
if (!used[x]) {
used[x] = true;
X.push_back(x);
}
}
// Clean up 'used' array for future use without O(M) fill
for (long long x : X) used[x] = false;
long long ans1 = collisions(X);
static vector<int> freq(3000005, 0);
fill(freq.begin(), freq.begin() + M + 1, 0);
// Compute frequencies of all absolute differences in X
for (int i = 0; i < K1; ++i) {
long long xi = X[i];
for (int j = i + 1; j < K1; ++j) {
// FIXED WARNING: changed int to long long
long long diff = xi - X[j];
if (diff < 0) diff = -diff;
freq[diff]++;
}
}
// Find all candidate n's that produce exactly ans1 collisions
vector<int> candidates;
for (int n = 2; n <= 1000000; ++n) {
long long c = 0;
for (int m = n; m <= M; m += n) {
c += freq[m];
}
if (c == ans1) {
candidates.push_back(n);
}
}
int queries = 1;
// Filter candidates until 1 is left (or we hit our safety limit of 10 queries)
while (candidates.size() > 1 && queries < 10) {
vector<long long> X_next;
while (X_next.size() < K_new) {
long long x = uniform_int_distribution<long long>(1, M)(rng);
if (!used[x]) {
used[x] = true;
X_next.push_back(x);
}
}
for (long long x : X_next) used[x] = false;
long long ans = collisions(X_next);
queries++;
vector<int> next_candidates;
for (int n : candidates) {
long long c = 0;
// Simulate collisions for candidate n in O(K_new) time
for (long long x : X_next) {
int rem = x % n;
c += count_arr[rem];
count_arr[rem]++;
}
if (c == ans) {
next_candidates.push_back(n);
}
// Rollback count_arr cleanly
for (long long x : X_next) {
count_arr[x % n] = 0;
}
}
candidates = next_candidates;
}
if (!candidates.empty()) {
return candidates[0];
}
return 2; // Fallback
}
// =====================================================================
// LOCAL GRADER FOR TESTING IN VISUAL STUDIO
// This part will be ignored by the online judge.
// =====================================================================
#ifdef nONLINE_JUDGE
int hidden_n;
long long total_cost = 0;
long long collisions(std::vector<long long> x) {
total_cost += x.size();
long long cols = 0;
vector<int> buckets(hidden_n, 0);
for (long long val : x) {
int rem = val % hidden_n;
cols += buckets[rem];
buckets[rem]++;
}
return cols;
}
int main() {
// Example test case
int t;
cout << "Enter number of test cases: ";
if (!(cin >> t)) return 0;
while (t--) {
cout << "Enter hidden n: ";
cin >> hidden_n;
total_cost = 0;
int result = hack();
cout << "Guessed n: " << result << " | Total Cost: " << total_cost << "\n";
if (result == hidden_n) {
cout << "Correct!\n";
}
else {
cout << "Wrong Answer!\n";
}
cout << "-----------------------\n";
}
return 0;
}
#endif
