Submission #337151

#	Time	Username	Problem	Language	Result	Execution time	Memory
337151		CaroLinda	Gap (APIO16_gap)	C++14	100 / 100	53 ms	2028 KiB

gap

#include "gap.h"
#include <bits/stdc++.h>

#define all(x) x.begin(),x.end()
#define sz(x) (int)(x.size() )
#define ll long long 

const ll MAX = 1e18 ;

using namespace std ;

long long findGap(int T, int N)
{
	
	if( T == 1 || N <= 7 )
	{
		vector<ll> a(N) ;

		MinMax(0LL,MAX, &a[0] , &a[N-1] ) ;

		for(int l = 1 , r = N-2 ; l <= r ; l++ , r-- )
			MinMax(a[l-1]+1, a[r+1]-1, &a[l], &a[r] ) ;
		
		ll resp = -1LL ;

		for(int i = 0 ; i < N-1 ; i++ ) resp = max(resp, a[i+1]-a[i] ) ;

		return resp ; 

	}

	ll cur = -1 ,mn=-1 , mx=-1 , biggest=-1 ;

	MinMax(0, MAX, &cur, &biggest ) ;

	ll d = (biggest-cur+N)/N ;

	while( true )
	{

		if( cur + d > biggest ) return d ;				

		MinMax(cur+1, cur+d, &mn, &mx ) ;

		if( mx != -1 ) 
		{
			cur = mx ; 
			continue ;
		}

		ll l = cur+d+1, r = cur + (d<<1LL) ;

		while( true )
		{
			MinMax(l, min(r, biggest), &mn, &mx ) ;

			if( r >= biggest ) return ( mn == -1 ) ? d : (mn-cur) ;
		
			if( mn != -1 )
			{
				d = mn - cur ;
				cur = mn ;
				break ;
			}			

			ll auxL = r+1 ;
			ll auxR = cur+((r-cur)<<1LL );

			l = auxL ;
			r = auxR ;
	 	
		}
	}

	return d ;

}

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