Submission #109798

#	Time	Username	Problem	Language	Result	Execution time	Memory
109798		boatinw99	Gap (APIO16_gap)	C++11	30 / 100	66 ms	2460 KiB

gap

#include "gap.h"
#include<bits/stdc++.h>
using namespace std ;
typedef long long ll ;
const ll inf = 1e18 ;
vector<ll> v ;
void push(ll cst)
{
    if(cst>-1)v.emplace_back(cst);
}
ll findGap(int T, int N)
{
    ll mn=0,mx=0,l=0,r=inf ;
    v.clear();
    if(T==1)
    {
        for(int i=1;i<=(N+1)/2;i++)
        {
            MinMax(l,r,&mn,&mx);
            push(mn),push(mx);
            l=mn+1,r=mx-1;
        }
    }
    else
    {
        MinMax(l,r,&mn,&mx);
        l=mn,r=mx;
        push(mn),push(mx);
        if(N!=2)
        {
            ll len = (mx-mn+1)/N;
            for(ll i=mn+1;i+len<=mx;i+=len)
            {
                MinMax(i,i+len,&mn,&mx);
                push(mn),push(mx);
            }            
        }
    }
    sort(v.begin(),v.end());
    ll ret = 0 ;
    for(int i=1;i<(int)v.size();i++)ret=max(ret,v[i]-v[i-1]);
    return ret ;
}

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