Submission #1217550

#TimeUsernameProblemLanguageResultExecution timeMemory
1217550uroskHack (APIO25_hack)C++20
40.60 / 100
441 ms4476 KiB
#include "hack.h" #include "bits/stdc++.h" #define pb push_back #define dbg(X) cerr<<#X<<": "<<X<<endl #define si(a_) (ll)(a_.size()) #define fi first #define all(a_) a_.begin(),a_.end() #define sc second #define popb pop_back #define ceri(a_,l_,r_) {for(ll i_ = l_;i_<=r_;i_++) cerr<<a_[i_]<< " ";cerr<<endl;} using namespace std; using ll = long long; using pll = pair<ll,ll>; 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; /** 1 1000000000 **/ ll tres = 40000; ll m = 30000; vector<ll> con(vector<ll> a,vector<ll> b){ while(si(b)){ a.pb(b.back()); b.popb(); } return a; } pll reshi(vector<ll> v){ if(si(v)==2) return {v[0],v[1]}; vector<ll> vl,vr; ll mid = si(v)/2; lol:; vl.clear(); vr.clear(); shuffle(all(v),rng); for(ll i = 0;i<=mid;i++) vl.pb(v[i]); for(ll i = mid+1;i<si(v);i++) vr.pb(v[i]); if(collisions(vl)) return reshi(vl); if(collisions(vr)) return reshi(vr); if(si(v)>15000) goto lol; vector<ll> vll,vlr; vector<ll> vrl,vrr; for(ll i = 0;i<si(vl);i++){ if(i<=si(vl)/2) vll.pb(vl[i]); else vlr.pb(vl[i]); } for(ll i = 0;i<si(vr);i++){ if(i<=si(vr)/2) vrl.pb(vr[i]); else vrr.pb(vr[i]); } vector<vector<ll> > koji; koji.pb(con(vll,vrl)); koji.pb(con(vll,vrr)); koji.pb(con(vlr,vrr)); koji.pb(con(vlr,vrl)); for(auto it : koji){ if(si(it)){ if(collisions(it)) return reshi(it); } } cerr<<"A"<<endl; if(si(v)<=tres){ ll tl = 0,tr = si(vr)-1,mid,rez = -1; while(tl<tr){ mid = (tl+tr)/2; w.clear(); for(ll i : vl) w.pb(i); for(ll i = tl;i<=mid;i++) w.pb(vr[i]); if(collisions(w)) rez = mid,tr = mid; else tl = mid+1; } ll R = tr; for(ll x : vl){ if(collisions({x,vr[R]})) return {x,vr[R]}; } } while(1){ vl.clear(); vr.clear(); shuffle(all(v),rng); for(ll i = 0;i<=mid;i++) vl.pb(v[i]); for(ll i = mid+1;i<si(v);i++) vr.pb(v[i]); if(collisions(vl)) return reshi(vl); if(collisions(vr)) return reshi(vr); } } int hack(){ ll c = -1; if(collisions({1,2})) return 1; ll mxv = 5*mx; for(ll t = 0;;t++){ 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; // dbg(cnt); //dbg(t); pll p = reshi(v); c = abs(p.fi-p.sc); break; } //dbg(c); 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...