Submission #1150619

#	Time	Username	Problem	Language	Result	Execution time	Memory
1150619		danglayloi2	Gap (APIO16_gap)	C++20	70 / 100	44 ms	1968 KiB

gap

#include "gap.h"
#include <bits/stdc++.h>
#define ii pair<int, int>
#define fi first
#define se second
#define inf 0x3f3f3f3f3f3f3f3f
using namespace std;
using ll = long long;
const ll mod=1e9+7;
const int nx=1e5+5;
ll findGap(int sub, int n)
{
    ll a[nx];
    if(sub==1)
    {
        ll l=0, r=1e18, mn, mx;
        int i=1, j=n;
        while(i<j)
        {
            MinMax(l, r, &mn, &mx);
            a[i]=mn, a[j]=mx;
            i++, j--;
            l=mn+1, r=mx-1;
        }
        ll res=0;
        for(int i = 1; i < n; i++)
            res=max(res, a[i+1]-a[i]);
        return res;
    }
    ll l, r;
    MinMax(0, 1e18, &l, &r);
    if(r-l+1==n)
        return 1;
    ll lim=r, gap=ceil(1.0*(r-l)/(n-1)), cur=l, nxt=l, res=0;
    while(cur<lim)
    {
        MinMax(cur+1, cur+gap, &l, &r);
        if(l!=-1)
        {
            res=max(res, l-nxt);
            nxt=r;
        }
        cur+=gap;
    }
    res=max(res, lim-nxt);
    return res;
}

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