Submission #1160463

#	Time	Username	Problem	Language	Result	Execution time	Memory
1160463		Doncho_Bonboncho	Gap (APIO16_gap)	C++17	30 / 100	38 ms	1864 KiB

gap

#include <algorithm>
#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;

struct Node{
	ll fir;
	ll lst;
	ll nas;
};

ll globNas = -1;
Node merge( const Node& a, const Node& b ){
	Node nas;
	nas.fir = a.fir;
	if( a.fir == -1 ) nas.fir = b.fir;
	nas.lst = b.lst;
	if( b.lst == -1 ) nas.lst = a.lst;

	ll currNas = b.fir - a.lst;
	if( b.fir == -1 || a.lst == -1 ) currNas = 0;
	cerr << out( currNas ) << endl;
	nas.nas = std::max({ a.nas, b.nas, currNas });

	cerr << out( a.fir ) << out( a.lst ) << out( a.nas ) << endl;
	cerr << out( b.fir ) << out( b.lst ) << out( b.nas ) << endl;
	cerr << out( nas.fir ) << out( nas.lst ) << out( nas.nas ) << endl << endl;
	chkmax( globNas, nas.nas );
	return nas;
}

struct Node sol( ll l, ll r ){

	if( globNas > ( r - l + 1 ) ){
		Node ret;
		ret.fir = ret.lst = ret.nas = -1;
		return ret;
	}

	ll mn, mx;
	MinMax( l, r, &mn, &mx );

	cerr << out( l ) << out( r ) << out( mn ) << out( mx ) << endl;

	if( mn == mx ){
		Node ret;
		ret.nas = -1;
		ret.fir = ret.lst = mn;
		return ret;
	}

	ll m = ( l + r ) >> 1;
	Node left = sol( l, m );
	Node right = sol( m+1, r );

	return merge( left, right );
}

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 );

		Node nas = sol( fir-1, lst+1 );
		cerr << out( nas.fir ) << out( nas.lst ) << out( nas.nas ) << endl;
		return nas.nas;
	}
}

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