| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 1209467 | khanhphucscratch | Hack (APIO25_hack) | C++20 | 0 ms | 0 KiB |
//#include "hack.h"
#include<bits/stdc++.h>
#define int long long
using namespace std;
int ansn, debug = 0;
mt19937_64 rng(chrono::high_resolution_clock::now().time_since_epoch().count());
int rnd(int l, int r)
{
int x = rng()%(r-l+1);
return x+l;
}
int collisions(vector<int> a)
{
map<int, int> f; debug += a.size();
for(int i : a) f[i%ansn]++;
int ans = 0;
for(pair<int, int> i : f) ans += i.second * (i.second-1)/2;
return ans;
}
pair<int, int> find_collision_pair(vector<int> question)
{
if(question.size() == 2) return {question[0], question[1]};
int mid = (question.size()-1)/2;
vector<int> nq;
while(true){
shuffle(question.begin(), question.end(), rng);
nq.clear();
for(int i = 0; i <= mid; i++) nq.push_back(question[i]);
if(collisions(nq) > 0){
break;
}
}
return find_collision_pair(nq);
}
int32_t hack()
{
//Subtask 1;
vector<int> question;
const int iteration = 60000;
set<int> st;
while(st.size() < iteration) st.insert(rnd(1, 1e12));
for(int i : st) question.push_back(i);
//This should contains some collisions, otherwise I'm doom to fail
pair<int, int> a = find_collision_pair(question);
int dif = abs(a.first - a.second);
vector<int> candidate;
for(int i = 1; i * i <= dif; i++) if(dif%i == 0){
candidate.push_back(i);
if(i*i < dif) candidate.push_back(dif/i);
}
sort(candidate.begin(), candidate.end());
for(int i : candidate) if(collisions({i, 2*i}) == 1) return i;
return -1; //This shouldn't happen
}
signed main()
{
cin>>ansn;
cout<<hack()<<endl<<debug;
}