Submission #1077473

#	Time	Username	Problem	Language	Result	Execution time	Memory
1077473		Icelast	Gap (APIO16_gap)	C++17	30 / 100	35 ms	2220 KiB

gap

#include "gap.h"
#include <iostream>
#include <bits/stdc++.h>
#define ll long long
using namespace std;
const ll maxn = 2*1e5+5, INF = 4e18+9;

long long findGap(int T, int n)
{
    ll ans = 0;
    if(T == 1){
        ll l = 0, r = INF;
        ll mn, mx;
        vector<ll> a(n+1);
        for(int i = 1; i <= (n+1)/2; i++){
            MinMax(l, r, &mn, &mx);
            a[i] = mn; a[n-i+1] = mx;
            l = mn+1, r = mx-1;
        }
        for(int i = 2; i <= n; i++){
            ans = max(ans, a[i]-a[i-1]);
        }
    }else{
        ll l = 0, r = INF;
        ll mn, mx;
        vector<ll> a(n+1);
        MinMax(l, r, &mn, &mx);
        l = mn, r = mx;
        ll d = ceil((r-l)/(n-1));
        while(l < r){
            MinMax(l+1, l+d, &mn, &mx);
            if(mn != -1){
                l = mx;
                continue;
            }

            MinMax(l+1, l+d*2, &mn, &mx);
            ll t = mn;

            while(t == -1){
                d*=2;
                MinMax(l+1, l+d*2, &mn, &mx);
                t = mn;
            }
            d = max(d, t-l);
            l = mx;
        }
        ans = d;
    }
	return ans;
}

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