Submission #1209467

#TimeUsernameProblemLanguageResultExecution timeMemory
1209467khanhphucscratchHack (APIO25_hack)C++20
Compilation error
0 ms0 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; }

Compilation message (stderr)

/usr/bin/ld: /tmp/cc0HVy0L.o: in function `collisions(std::vector<long long, std::allocator<long long> >)':
grader.cpp:(.text+0x470): multiple definition of `collisions(std::vector<long long, std::allocator<long long> >)'; /tmp/ccp77q8o.o:hack.cpp:(.text+0x840): first defined here
/usr/bin/ld: /tmp/cc0HVy0L.o: in function `main':
grader.cpp:(.text.startup+0x0): multiple definition of `main'; /tmp/ccp77q8o.o:hack.cpp:(.text.startup+0x0): first defined here
collect2: error: ld returned 1 exit status