Submission #464764

#	Time	Username	Problem	Language	Result	Execution time	Memory
464764		Killer2501	Gap (APIO16_gap)	C++14	0 / 100	3090 ms	1108 KiB

gap

#include <bits/stdc++.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
#include "gap.h"
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);
        while(l <= r)
        {
            MinMax(l+1, r-1, &mn, &mx);
            if(mn == -1)
            {
                ans = max(ans, r-l);
                break;
            }
            ans = max(ans, max(mn-l, r-mx));
            l = mn;
            r = mx;
            if(l == r)break;
        }
        return ans;
    }
    else
    {
        ll l = 0, r = 1e18, mn, mx, ans = 0;
        MinMax(l, r, &mn, &mx);
        l = mn+1;
        r = mx;
        ll lst = mn;
        ll len = (mx - mn) / (n - 1);
        ans = len;
        for(int i = l; i < r; i += len)
        {
            MinMax(i, i+len, &mn, &mx);
            if(mn == -1)continue;
            ans = max(ans, mn-lst);
            lst = mx;
        }
        return ans;
    }
}

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