Submission #1160501

#	Time	Username	Problem	Language	Result	Execution time	Memory
1160501		Doncho_Bonboncho	Gap (APIO16_gap)	C++17	89.04 / 100	64 ms	5700 KiB

gap

#include <algorithm>
#include <exception>
#include <random>
#include <stdio.h>
#include <stdlib.h>
#include <vector>

#include "gap.h"
#include <bits/stdc++.h>
using namespace std;

#ifndef LOCAL
#define cerr if(false) cerr
#endif

#define out( x ) #x << " = " << x << "  "
#define endl "\n"

template<class T, class T2> inline bool chkmax(T &x, const T2 &y) { return x < y ? x = y, 1 : 0; }
template<class T, class T2> inline bool chkmin(T &x, const T2 &y) { return x > y ? x = y, 1 : 0; }

typedef long long ll;
const ll mod = 1e9 +7;
const int MAX_N = 1e6 + 42;


ll a[MAX_N];
long long findGap(int subtask, int n){

	if( subtask == 1 ){


		ll lInd = 0;
		ll rInd = n-1;

		ll mn=0;
		ll mx=1e18;
		while( lInd <= rInd ){
			MinMax( mn, mx, &a[lInd ++],&a[rInd --]);

			mn = a[lInd-1]+1;
			mx = a[rInd+1]-1;
		}

		ll nas = 0;
		for( int i=0 ; i < n-1 ; i++ ){
			cerr << out( i ) << out( a[i+1] - a[i] ) << endl;
			chkmax( nas, ll( a[i+1] - a[i] ) );
		}

		cerr << out( nas ) << endl;
		return nas;
	}else{

		ll fir, lst;
		MinMax( -1, 1e18, &fir, &lst );

		std::set< ll > s;
		s.insert( fir );
		s.insert( lst );

		ll gap = ( lst - fir ) / ( n - 1 );
		if( gap == 0 ) return -1;

		cerr << out( gap ) << endl;
		for( ll j=fir+1 ; j < lst ; j += gap ){
			ll mn, mx;
			MinMax( j, j + gap-1, &mn, &mx );
			if( mn != -1 ) s.insert( mn );
			if( mx != -1 ) s.insert( mx );
		}

		ll nas = -1;
		for( auto it = s.begin() ; next( it ) != s.end() ; it++ ){
			ll currNas = *(next( it ) ) - *it;
			chkmax( nas, currNas );
		}

		cerr << out( nas ) << endl;
		return nas;
	}
}

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