Submission #448942

#	Time	Username	Problem	Language	Result	Execution time	Memory
448942		JovanB	Gap (APIO16_gap)	C++17	100 / 100	68 ms	1856 KiB

gap

#include "gap.h"
#include <bits/stdc++.h>
 
using namespace std;
 
typedef long long ll;
 
const ll INF = 1000000000000000000LL;
 
ll a[100005];
 
long long findGap(int T, int N){
 
    if(T == 1){
        int l = 1, r = N;
        a[N+1] = INF+1;
        while(l <= r){
            MinMax(a[l-1]+1, a[r+1]-1, &a[l], &a[r]);
            l++;
            r--;
        }
        ll res = 0;
        for(int i=2; i<=N; i++) res = max(res, a[i]-a[i-1]);
        return res;
    }
    ll mn, mx;
    MinMax(1, INF, &mn, &mx);
    ll block = (mx-mn+N-2)/(N-1);
    ll res = block;
    ll posl = mn;
    ll i;
    for(i=mn; i+block+1 <= mx; i += block+1){
        ll a, b;
        MinMax(i, i+block+1, &a, &b);
        if(a == -1) continue;
        res = max(res, a-posl);
        posl = b;
    }
    ll a, b;
    MinMax(i, mx, &a, &b);
    if(a != -1) res = max(res, a-posl);
	return res;
}

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