#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;
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);
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 time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |