Submission #1211039

#	Time	Username	Problem	Language	Result	Execution time	Memory
1211039		hengliao	Hack (APIO25_hack)	C++20	In queue	0 ms	0 KiB

hack

#include "hack.h"
#include<bits/stdc++.h>
using namespace std;

#define F first
#define S second
#define pll pair<ll, ll>
#define vll vector<ll>
#define pb push_back

typedef long long ll;

namespace{

    const ll mxN=1e6;

    vll f(ll a, ll b){
        ll len=b-a+1;
        ll B=sqrt(len);
        vll re;
        for(ll i=1;i<=B;i++){
            re.pb(i);
        }
        ll cur=B+a;
        while(true){
            re.pb(cur);
            if(cur-1==b) break;
            cur=min(cur+B, b+1);
        }
        return re;
    }
}


int hack(){
    ll lef=2, rig=mxN;

    while(lef<rig){
        ll mid=(lef+rig)/2;
        if(collisions(f(lef, mid))>0){
            rig=mid;
        }
        else{
            lef=mid+1;
        }
    }

    return (int) lef;
}