Submission #231311

#	Time	Username	Problem	Language	Result	Execution time	Memory
231311		peijar	Gap (APIO16_gap)	C++17	100 / 100	77 ms	3308 KiB

gap

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

#define SZ(v) ((int)(v).size())
using ll = long long;

void MinMax(ll lo, ll up, ll *mn, ll *mx);

ll findGap(int sous_tache, int nb_elem)
{
	if (sous_tache == 2)
	{
		ll smallest, biggest;
		MinMax((ll)0, (ll)1e18, &smallest, &biggest);
		ll delta = ceil( (long double)(biggest - smallest) / (nb_elem - 1));

		vector<ll> sparse_elem;
		for (ll k(0); k < nb_elem - 1; ++k)
		{
			ll l, r;
			MinMax(smallest + k * delta, smallest + (k+1) * delta-1, &l, &r);
			if (l != -1)
			{
				sparse_elem.push_back(l);
				sparse_elem.push_back(r);
			}
		}
		sparse_elem.push_back(biggest);
		ll ans = delta;
		for (int i(0); i + 1 < SZ(sparse_elem); ++i)
			ans = max(ans, sparse_elem[i+1] - sparse_elem[i]);
		return ans;
	}
	else
	{
		ll arr[nb_elem];
		MinMax(0LL, (ll)1e18, arr, arr + nb_elem - 1);
		for (int i(1), j(nb_elem - 2); i <= j; i++, j--)
			MinMax(arr[i-1]+1, arr[j+1] - 1, arr + i, arr + j);
		ll ans(0);
		for (int i(0); i < nb_elem-1; ++i)
			ans = max(ans, arr[i+1] - arr[i]);
		return ans;
	}
}

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