제출 #1217489

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1217489		urosk	Hack (APIO25_hack)	C++20	35.70 / 100	540 ms	7116 KiB

hack

#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 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 = 5000;
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);
    if(si(v)<=tres){
        ll tl = 0,tr = si(v)-1,mid,rez = -1;
        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;
        return {v[L],v[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 m = 65000;
    ll c = -1;
    if(collisions({1,2})) return 1;
    ll mxv = 100*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 ;
}

• Subtask 0: 0 / 0
• Subtask 1: 8 / 8
• Subtask 2: 17 / 17
• Subtask 3: 10.6883 / 75