Submission #464769

#	Time	Username	Problem	Language	Result	Execution time	Memory
464769		Killer2501	Gap (APIO16_gap)	C++14	100 / 100	63 ms	1184 KiB

gap

#include <bits/stdc++.h>
#include "gap.h"
#define ll long long
#define pb push_back
#define task "asd"
#define pll pair<ll, ll>
#define pii pair<pll, ll>
#define fi first
#define se second

using namespace std;
const ll mod = 1e9+7;
const ll N = 2e5+5;
const int base = 313;
ll findGap(int t, int n)
{
    if(t == 1)
    {
        ll l = 0, r = 1e18, mn, mx, ans = 0;
        MinMax(l, r, &mn, &mx);
        l = mn, r = mx;
        for(int i = 1; i < (n+1)/2; i ++)
        {
            MinMax(l+1, r-1, &mn, &mx);
            ans = max(ans, max(mn-l, r-mx));
            l = mn;
            r = mx;
        }
        return max(ans, r-l);
    }
    else
    {
        ll l = 0, r = 1e18, mn, mx, ans = 0;
        MinMax(l, r, &mn, &mx);
        ll lst = mn;
        ll len = (mx - mn) / (n - 1);
        ans = len;
        l = mn, r = mx;
        for(ll i = l; i < r; i += len+1)
        {
            MinMax(i, i+len, &mn, &mx);
            if(mn == -1)continue;
            ans = max(ans, mn-lst);
            lst = mx;
        }
        return ans;
    }
}

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