Submission #274823

#	Time	Username	Problem	Language	Result	Execution time	Memory
274823		test2	Gap (APIO16_gap)	C++14	89.04 / 100	80 ms	3468 KiB

gap

#include <bits/stdc++.h>
#include <stdlib.h>

#include "gap.h"

#define I inline void 

using ll = long long ; 
using ld = long double ; 

using namespace std ; 

const int mod = 1e9 + 7 ; 

long long findGap(int T, int N)
{
	ll ans = 0 ; 
	if(T == 1){
		ll lo = 0, hi = 1e18 ; 

		multiset<ll> s ; 
		int l = 0 , r = N - 1; 
		vector<ll> arr(N+1 , 0) ; 
		while(l<=r){
			ll mn ,mx ; 
			MinMax(lo , hi , &mn , &mx) ; 
			arr[l] = mn ; 
			arr[r] = mx ; 
			l++ ; 
			r-- ; 
			lo = mn + 1 ; 
			hi = mx - 1; 
		}
		for(int i =1 ;i < N ;i++)
			ans = max(ans , arr[i] - arr[i-1]) ;
	}
	else{

		ll mn , mx ; 
		MinMax(0 , 1e18 , &mn , &mx) ; 
		ll d = (mx - mn - 1) / (N - 1) ;
		vector<ll> vec = {mn , mx } ; 

		ll cur = mn + 1 ; 

		while(cur < vec[1]){
			MinMax(cur , min(vec[1] - 1, cur + d - 1 ) , &mn , &mx) ; 
			cur+=d ; 
			if(mn == -1){
				continue ; 
			}
			vec.push_back(mn) ; 
			vec.push_back(mx) ; 
			if(ans > vec[1] - vec.back())break ;
		}
		sort(vec.begin() , vec.end()) ; 
		for(int i = 1 ; i < (int) vec.size() ;i ++){
			ans = max(ans , vec[i] - vec[i-1] ) ; 
		}

	}

	return ans ; 
}

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