Submission #1217462

#TimeUsernameProblemLanguageResultExecution timeMemory
1217462uroskHack (APIO25_hack)C++20
25 / 100
776 ms9156 KiB
#include "hack.h" #include "bits/stdc++.h" #define pb push_back #define dbg(X) cerr<<#X<<": "<<X<<endl #define ceri(a_,l_,r_) {for(ll i_ = l_;i_<=r_;i_++) cerr<<a_[i_]<< " ";cerr<<endl;} using namespace std; using ll = long long; ll n; mt19937_64 rng(time(0)); ll rnd(ll l,ll r){return uniform_int_distribution<ll>(l,r)(rng);} map<ll,bool> tu; vector<ll> v,w; ll mx = 1000000000; int hack(){ ll m = 100000; ll c = -1; if(collisions({1,2})) return 1; ll mxv = 2*mx; while(1){ v.clear(); tu.clear(); for(ll i = 0;i<m;i++){ ll x = rnd(1,mxv); if(tu[x]) i--; else{ v.pb(x); tu[x] = 1; } } ll cnt = collisions(v); if(cnt==0) continue; ll tl = 0,tr = m-1,mid,rez; while(tl<=tr){ mid = (tl+tr)/2; w.clear(); for(ll i = 0;i<=mid;i++) w.pb(v[i]); if(collisions(w)) rez = mid,tr = mid-1; else tl = mid+1; } ll R = rez; tl = 0,tr = R,rez = -1; while(tl<=tr){ mid = (tl+tr)/2; w.clear(); for(ll i = mid;i<=R;i++) w.pb(v[i]); if(collisions(w)) rez = mid,tl = mid+1; else tr = mid-1; } ll L = rez; c = abs(v[L]-v[R]); break; } ll ans = c; for(ll i = 2;i*i<=c;i++){ if(c%i==0){ //dbg(i); if(collisions({1,i+1})) ans = min(ans,i); if(i*i!=c){ //dbg(c/i); if(collisions({1,c/i+1})) ans = min(ans,c/i); } } } return ans ; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...