Submission #636878

#	Time	Username	Problem	Language	Result	Execution time	Memory
636878		lovrot	Gap (APIO16_gap)	C++11	30 / 100	43 ms	2732 KiB

gap

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

#define X first
#define Y second
#define ll long long

const int N = 100010;
const ll INF = 1e18;

using namespace std;

ll niz[N];

ll findGap(int t, int n){
	if(t == 1){ 
		int minp = 0;
		int maxp = n - 1;
		ll mn = 0, minr;
		ll mx = INF, maxr;
 
		while(minp <= maxp){ 
			MinMax(mn, mx, &minr, &maxr);
			niz[minp] = minr;
			niz[maxp] = maxr;
			mn = minr + 1;
			mx = maxr - 1; 
			minp++;
			maxp--;
		}
 
		ll ans = 0;
		for(int i = 0; i < n - 1; i++) ans = max(ans, niz[i + 1] - niz[i]);
		return ans;
	}
	ll mn = 0;
	ll mx = INF;
	MinMax(mn, mx, &mn, &mx);
	niz[n - 1] = mx;
	niz[0] = mn;

	for(int i = n - 2; i > 0; i--){ 
		mx--;
		mn = mx;
		MinMax(mn, mx, &mn, &mx);
		niz[i] = mx;
		assert(mx != -1);
	}

	ll ans = 0;
	for(int i = 0; i < n - 1; i++) ans = max(ans, niz[i + 1] - niz[i]);
	return ans;
}

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