Submission #850074

#	Time	Username	Problem	Language	Result	Execution time	Memory
850074		TahirAliyev	Gap (APIO16_gap)	C++17	30 / 100	40 ms	3108 KiB

gap

#include "gap.h"
#include <bits/stdc++.h>

using namespace std;

#define ll long long

ll findGap(int T, int N)
{
    if(T == 1){
        ll a, b;
        MinMax(1, 1e18, &a, &b);
        if(N == 2){
            return b - a;
        }
        ll ans = 1;
        ll _a, _b;
        int t = 2;
        while(t < N){
            _a = a, _b = b;
            MinMax(a + 1, b - 1, &a, &b);
            ans = max(a - _a, ans);
            ans = max(_b - b, ans);
            t += 2;
        }
        if(N % 2 == 0){
            ans = max(ans, b - a);
        }
        return ans;
    }
    else{
        ll l, r;
        MinMax(1, 1e18, &l, &r);
        if(N == 2){
            return r - l;
        }
        ll g = ceil(double(l + r) / (N - 1));
        ll ans = g - 1;
        ll cur = l;
        l++;
        while(l <= r){
            ll nl, nr;
            MinMax(l, l + g - 1, &nl, &nr);

            ans = max(ans, nl - cur);
            if(nl != -1){
                cur = nr;
            }
            l = l + g;
        }
        return ans;
    }
}

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