제출 #732236

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
732236		1ne	Gap (APIO16_gap)	C++14	30.51 / 100	56 ms	2236 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;
		vector<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;
					MinMax(s + 1,mid,&x,&y);
					if (x == -1 && y == -1){
						s = mid;
						left = mid + 1;
					}
					else{
						pos.push_back(y);
						if (x != y){
							pos.push_back(x);
						}
						right = mid - 1;
					}
				}
				sort(pos.rbegin(),pos.rend());
			}
			if (pos.back() < s)pos.pop_back();
			else if (pos.back() == s){
				v.push_back(pos.back());
				pos.pop_back();
				++s;
				++i;
			}
			else{
				MinMax(s,pos.back(),&x,&y);
				if (x == -1 && y == -1){
					s = pos.back() + 1;
					pos.pop_back();
				}
				else{
					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.5074223417 / 70