Submission #732238

#	Time	Username	Problem	Language	Result	Execution time	Memory
732238		1ne	Gap (APIO16_gap)	C++14	30 / 100	3088 ms	2256 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;
		vector<long long>v;
		set<long long>pos;
		long long s = 0;	
		for (int i = 0;i<N;){
			if (pos.empty()){
				long long left = s + 1,right = 1e18;
				while(left<=right){
					long long mid = (left + right)>>1;
					if (s + 1 > mid){
						x = -1,y = -1;
					}
					else{
						MinMax(s + 1,mid,&x,&y);
					}
					if (x == -1 && y == -1){
						s = mid + 1;
						left = mid + 1;
					}
					else{
						pos.insert(y);
						if (x != y){
							pos.insert(x);
						}
						right = mid - 1;
					}
				}                             
			}
			if (*pos.begin() < s)pos.erase(pos.begin());
			else if (*pos.begin() == s){
				v.push_back(*pos.begin());
				pos.erase(pos.begin());
				++s;
				++i;
			}
			else{
				MinMax(s,*pos.begin(),&x,&y);
				if (x == -1 && y == -1){
					s = *pos.begin() + 1;
					pos.erase(pos.begin());
				}
				else{
					pos.insert(y);
					v.push_back(x);
					s = x + 1;
					++i;
				}
			}  	
		}
		sort(v.begin(),v.end());
		for (int i = 1;i<N;++i){
			ans = max(ans,v[i] - v[i - 1]);
		}	
	} 
	return ans;
}

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