Submission #1217667

#	Time	Username	Problem	Language	Result	Execution time	Memory
1217667		urosk	Hack (APIO25_hack)	C++20	84.90 / 100	62 ms	2520 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 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 = 22366;
vector<ll> con(vector<ll> a,vector<ll> b){
    while(si(b)){
        a.pb(b.back());
        b.popb();
    }
    return a;
}
pll reshi(vector<ll> vl,vector<ll> vr){
   // cerr<<si(vl)<< " "<<si(vr)<<" "<<collisions(con(vl,vr))<<endl;
    if(si(vl)==2&&si(vr)==0){
        //ceri(vl,0,1);
        return {vl[0],vl[1]};
    }
    if(si(vr)==2&&si(vl)==0){
        //ceri(vr,0,1);
        return {vr[0],vr[1]};
    }

    if(si(vl)==1&&si(vr)==1){
            return {vl[0],vr[0]};
    }
    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]);
    }
    if(collisions(con(vll,vrl))) return reshi(vll,vrl);
    if(collisions(con(vll,vrr))) return reshi(vll,vrr);
    if(collisions(con(vlr,vrl))) return reshi(vlr,vrl);
    return reshi(vlr,vrr);
}
vector<ll> vl,vr;
int hack(){
    ll c = -1;
    if(collisions({1,2})) return 1;
    ll mxv = 100*mx;
    vector<ll> pw2;
    pw2.pb(1);
    while(pw2.back()<mx) pw2.pb(pw2.back()*2);
    for(ll t = 0;;t++){
        vl.clear(); vr.clear();
        for(ll i = 1;i<=m;i++) vl.pb(i);
        for(ll i = 1;mx/2+i*m<=mx+m;i++) vr.pb(mx/2+i*m);

        //dbg(cnt);
        //dbg(t);
       // dbg(cnt);
       //dbg(si(vl));
       //dbg(si(vr));
        pll p = reshi(vl,vr);
        c = abs(p.fi-p.sc);
        dbg(c);
        break;
    }
    //dbg(c);
     vector<ll> pr;
    ll cc = c;
    for(ll i = 2;i*i<=c;i++){
        if(c%i==0){
            pr.pb(i);
            while(c%i==0) c/=i;
        }
    }
    if(c>1) pr.pb(c);
    for(ll x : pr){
        while(cc%x==0&&collisions({1,cc/x+1})) cc/=x;
    }
    vector<ll> df = {2,53,106,211,422,11183,22336};
    for(ll x : df) if(collisions({1,x+1})) cc = min(cc,x);
    return cc;
}

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