Submission #731291

#	Time	Username	Problem	Language	Result	Execution time	Memory
731291		1ne	Gap (APIO16_gap)	C++14	30 / 100	3088 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;
	MinMax(0,1e18,&x,&y);
	long long left = 2,right = 1e18;
		while(left<=right){
			long long mid = (left + right)>>1;
			long long s = x;
			bool ok = false;
			while(s < y){
				long long xx,yy;
				MinMax(s + 1,s + mid,&xx,&yy);
				if (yy == s + mid && xx == yy){
					ok = true;
					break;
				}
				s = yy;
			}
			if (ok){
				left = mid + 1;
				ans = mid;
			}
			else right = mid - 1;
		}
	} 
	return ans;
}

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