Submission #875934

#	Time	Username	Problem	Language	Result	Execution time	Memory
875934		Lobo	Gap (APIO16_gap)	C++17	100 / 100	42 ms	4048 KiB

gap

#include "gap.h"
#include<bits/stdc++.h>
using namespace std;
#define int long long

int findGap(int32_t T, int32_t n)
{

	if(T == 1) {
		int mn,mx;
		vector<int> a(n+1);
		MinMax(0,(int) 1e18,&mn,&mx);
		a[1] = mn;
		a[n] = mx;
		int l = 2;
		int r = n-1;
		while(l <= r) {
			MinMax(a[l-1]+1,a[r+1]-1,&a[l],&a[r]);
			l++;
			r--;
		}

		int ans = 0;
		for(int i = 1; i <= n-1; i++) ans = max(ans, a[i+1]-a[i]);
		return ans;
		
	}
	else {

		int a1,an;
		MinMax(0,(int) 1e18,&a1,&an);

		int gap = (an-a1+n-1-1)/(n-1);
		int gap0 = gap;
		int ant = a1;
		for(int i = a1; i <= an; i+= gap0+1) {
			int mn,mx;
			MinMax(i,i+gap0,&mn,&mx);

			if(mn == -1) continue;
			gap = max(gap,mn-ant);
			ant = mx;
		}
		return gap;
	}
}

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