Submission #732241

#	Time	Username	Problem	Language	Result	Execution time	Memory
732241		1ne	Gap (APIO16_gap)	C++14	100 / 100	51 ms	1872 KiB

gap

#include "gap.h"	
#include <bits/stdc++.h>
using namespace std;
long long findGap(int T, int N)
{
	long long ans = 1;
	if (T == 1){
		long long s = -1,t = 1e18 + 1;
		long long x = 0,y = 0;
		vector<long long>pos(N);
		int l = 0,r = N - 1;
		while(l <= r && s<=t){
			MinMax(s,t,&x,&y);
			if (x == -1 && y == -1){
				break;
			}
			pos[l] = x;
			pos[r] = y;
			--r;
			++l;
			s = x + 1;
			t = y - 1;	
		}
		sort(pos.begin(),pos.end());
		for (int i = 1;i<N;++i){
			ans = max(ans,pos[i] - pos[i - 1]);
		}
	}
	else{
		long long x,y,xx,yy;
		long long s = 0,t = 1e18,lst = 0;
		MinMax(s,t,&xx,&yy);
		lst = xx;
		long long block = (yy - xx - 2 + N) / (N - 1);
		for (long long i = xx + 1;i<=yy - 1;i+=block){
			MinMax(i,i + block - 1,&x,&y);
			if (x == -1)continue;
			ans = max(ans,x - lst);
			lst = y;
		}	
	} 
	return ans;
}

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