제출 #409733

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
409733		naranbat	Gap (APIO16_gap)	C++17	100 / 100	60 ms	1844 KiB

gap

#include "gap.h"
#include<bits/stdc++.h>
const long long INF = 1e18 + 6;
using namespace std;

long long a[100005];

long long findGap(int T, int N)
{
	if(T == 1){
		int l = 0;
		int r = N - 1;
		long long mn = 0, mx = INF;
		long long h,h1;
		while(l <= r){
			MinMax(mn, mx, &h, &h1);
			a[l] = h;
			a[r] = h1;
			l++;
			r--;
			mn = h + 1;
			mx = h1 - 1;
		}
		long long ans = 0;
		for(int i = 1; i < N; i++){
			ans = max(ans,a[i] - a[i - 1]);
		}
		return ans;
	}
	else{
		long long mn,mx;
		MinMax(0, INF, &mn, &mx);
		a[0] = mn;
		a[N] = mx;
		long long x = (mx - mn + N - 2) / (N - 1) + 1;

		long long ans = x - 1;
		long long l = mn + 1, last = mn;

		while(last + x < a[N]){
			MinMax(l, l + x - 1, &mn, &mx);
			if(mn == -1){
				l += x;
			} else{
				ans = max(ans, mn - last);
				last = mx;
				l = last + 1;
			}
			x = max(ans, x + 1);
		}
		return ans;
	}
}

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