| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 1368033 | am_aadvik | Hack (APIO25_hack) | C++20 | 0 ms | 0 KiB |
#pragma GCC optimize("O3,unroll-loops")
#include <iostream>
#include <vector>
#include <random>
#include <algorithm>
#include <chrono>
#define nONLINE_JUDGE
using namespace std;
#pragma GCC optimize("O3,unroll-loops")
//#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
#include <iostream>
#include <vector>
#include <random>
#include <algorithm>
#include <chrono>
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 freq[20000005];
bool used_arr[20000005];
int hack() {
int M = 20000000;
int MAX_N = 10000000; // Increased to cover Subtask 3
int K = 10000;
// Use a time-based seed to prevent any adversarial fixed test cases
static mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
// Initially, all numbers from 2 to 10,000,000 are candidates
vector<int> candidates;
candidates.reserve(MAX_N);
for (int n = 2; n <= MAX_N; ++n) {
candidates.push_back(n);
}
int total_cost = 0;
int max_cost = 110000; // Limit for full points
while (candidates.size() > 1 && total_cost < max_cost) {
// PHASE 2: Targeted Queries (Binary Search)
// When candidates are few, we can isolate them with queries of size 2
if (candidates.size() <= 5000) {
long long best_D = candidates[0];
int best_diff = candidates.size();
// Find a difference D that separates the remaining candidates in half
for (int D : candidates) {
int count = 0;
for (int n : candidates) {
if (D % n == 0) count++;
}
if (count > 0 && count < candidates.size()) {
int diff = abs(count - (int)candidates.size() / 2);
if (diff < best_diff) {
best_diff = diff;
best_D = D;
// Early exit if we found a D that splits them roughly 40%-60%
if (diff <= candidates.size() / 10 + 1) break;
}
}
}
// Query exactly 2 elements. Cost = 2.
vector<long long> X_test = { 1, 1 + best_D };
long long ans = collisions(X_test);
total_cost += 2;
vector<int> next_candidates;
for (int n : candidates) {
long long expected = (best_D % n == 0) ? 1 : 0;
if (expected == ans) {
next_candidates.push_back(n);
}
}
candidates = next_candidates;
}
// PHASE 1: Random Queries (Broad Search)
else {
if (total_cost + K > max_cost) break;
vector<long long> X;
X.reserve(K);
// Generate a random set of distinct numbers
while (X.size() < K) {
long long x = uniform_int_distribution<long long>(1, M)(rng);
if (!used_arr[x]) {
used_arr[x] = true;
X.push_back(x);
}
}
for (long long x : X) used_arr[x] = false;
long long ans = collisions(X);
total_cost += K;
fill(freq, freq + M + 1, 0);
sort(X.begin(), X.end());
// Compute frequencies of all absolute differences in X
for (int i = 0; i < K; ++i) {
int xi = X[i];
for (int j = i + 1; j < K; ++j) {
freq[X[j] - xi]++;
}
}
vector<int> next_candidates;
for (int n : candidates) {
long long c = 0;
for (int m = n; m <= M; m += n) {
c += freq[m];
}
if (c == ans) {
next_candidates.push_back(n);
}
}
candidates = next_candidates;
}
}
if (!candidates.empty()) {
return candidates[0];
}
return 2; // Fallback
}
// =====================================================================
// LOCAL GRADER FOR TESTING
// This part will be ignored by Codeforces.
// =====================================================================
#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 buckets.clear(), cols;
}
int main() {
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;
auto start = chrono::high_resolution_clock::now();
int result = hack();
auto end = chrono::high_resolution_clock::now();
double time_taken = chrono::duration_cast<chrono::milliseconds>(end - start).count();
cout << "Guessed n: " << result << " | Total Cost: " << total_cost << "\n";
cout << "Time taken: " << time_taken << " ms\n";
if (result == hidden_n) cout << "Correct!\n";
else cout << "Wrong Answer!\n";
cout << "-----------------------\n";
}
return 0;
}
#endif