Submission #489214

#	Time	Username	Problem	Language	Result	Execution time	Memory
489214		leaked	Gap (APIO16_gap)	C++14	86.51 / 100	70 ms	8864 KiB

gap

#include "gap.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
#define f first
#define s second

pair<ll,ll> ask(ll l,ll r){
    if(l>r) return {-1,-1};
    ll *a,*b;
    a=new long long(),b=new long long();
    MinMax(l,r,a,b);
    return {*a,*b};
}
long long findGap(int T, int N)
{
    if(T==1){
        long long x=0,y=1e18;
        vector<long long>vc;
        while(N>=1){
            long long *a,*b;
            a=new long long(),b=new long long();
            MinMax(x,y,a,b);
            x=*a,y=*b;
            vc.push_back(x);
            vc.push_back(y);
            x++;y--;
            N-=2;
        }
        sort(vc.begin(),vc.end());
        long long ans=0;
        for(int i=1;i<(int)vc.size();i++)
            ans=max(ans,vc[i]-vc[i-1]);
        return ans;
    }
    else{
        long long x=0;
        ll y=1e18;
        auto c=ask(x,y);
        x=c.f,y=c.s;
        ll d=ceil((ld)(y-x)/(N-1));
        ll ans=d;
//        d++;
        while(x+d<y){
            ll cnt=1;
            while(1){
                c=ask(x+1+(cnt-1)*d,min(y-1,x+cnt*d));
                if(c.f==-1 && x+cnt*d>=y){
                    ans=max(ans,y-x);
                    return ans;
                }
                if(c.f!=-1)
                    break;
                else
                    cnt++;
            }
            ans=max(ans,c.f-x);
            x=c.s;
        }
        ans=max(ans,y-x);
        return ans;
    }
	return 0;
}
/*
n+
*/

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