Submission #553358

#	Time	Username	Problem	Language	Result	Execution time	Memory
553358		urosk	Gap (APIO16_gap)	C++14	78.54 / 100	70 ms	3252 KiB

gap

#include "gap.h"
// __builtin_popcount(x)
// __builtin_popcountll(x)
#define here cerr<<"===========================================\n"
#include <bits/stdc++.h>
#define ld double
#define ll long long
#define ull unsigned long long
#define llinf 100000000000000000LL // 10^17
#define iinf 2000000000 // 2*10^9
#define pb push_back
#define popb pop_back
#define fi first
#define sc second
#define endl '\n'
#define pii pair<int,int>
#define pll pair<ll,ll>
#define pld pair<ld,ld>
#define sz(a) int(a.size())
#define all(a) a.begin(),a.end()
#define ceri(a,l,r) {for(ll i_ = l;i_<=r;i_++) cerr<<a[i_]<< " ";cerr<<endl;}
using namespace std;
ll n;
ll t;
ll findGap(int T, int N)
{
    n = N;
    t = T;
    if(t==1){
        ll l = 1,r = 1000000000;
        r*=r;
        vector<ll> v;
        while(l<=r){
            ll x,y;
            if(sz(v)==n) break;
            MinMax(l,r,&x,&y);
            if(x==-1&&y==-1) break;
            if(x==y){
                v.pb(x);
                break;
            }else{
                v.pb(x);
                v.pb(y);
                r = y-1;
                l = x+1;
            }
        }
        sort(all(v));
        ll ans = 0;
        for(ll i = 0;i<sz(v)-1;i++){
            ans = max(ans,v[i+1]-v[i]);
        }
        return ans;
    }
    ll l = 1,r = 1000000000;
    r*=r;
    ll mini,maxi;
    MinMax(l,r,&mini,&maxi);
    ll d = (maxi-mini)/(n-1);
    //cerr<<"d: "<<d<<endl;
    if(d==0) return 0;
    vector<ll> v = {mini,maxi};
    for(ll i = mini;i<=maxi;i+=d){
        ll x,y;
        ll l = i,r = i+d;
        MinMax(l,r,&x,&y);
        if(x==-1&&y==-1) continue;
        v.pb(x);
        v.pb(y);
    }
    ll ans = 0;
    sort(all(v));
    for(ll i = 0;i<sz(v)-1;i++) ans = max(ans,v[i+1]-v[i]);
	return ans;
}

• Subtask 1: 30 / 30
• Subtask 2: 48.5410196625 / 70