Submission #706802

#	Time	Username	Problem	Language	Result	Execution time	Memory
706802		600Mihnea	Gap (APIO16_gap)	C++17	70 / 100	60 ms	3644 KiB

gap

#include <cmath>
#include <functional>
#include <fstream>
#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <set>
#include <map>
#include <list>
#include <time.h>
#include <math.h>
#include <random>
#include <deque>
#include <queue>
#include <unordered_map>
#include <unordered_set>
#include <iomanip>
#include <cassert>
#include <bitset>
#include <sstream>
#include <chrono>
#include <cstring>
#include <numeric>

#include "gap.h"

using namespace std;

//long long findGap(int t, int n)
//{
//	long long ST = 0;
//	long long DR = (long long)1e18;
//	
//	vector<long long> a(n);
//
//	for (int i = 0; i <= n - 1 - i; i++)
//	{
//		MinMax(ST, DR, &ST, &DR);
//		int j = n - 1 - i;
//		a[i] = ST;
//		a[j] = DR;
//		ST++;
//		DR--;
//	}
//	long long best_gap = (a[n - 1] - a[0] + (n - 2)) / (n - 1);
//	for (int i = 0; i + 1 < n; i++)
//	{
//		best_gap = max(best_gap, a[i + 1] - a[i]);
//	}
//	return best_gap;
//}

long long findGap(int t, int n)
{
	long long ST = 0;
	long long DR = (long long)1e18;

	MinMax(ST, DR, &ST, &DR);
	
	long long best_gap = (DR - ST + (n - 2)) / (n - 1);
//cout << "\t\t\t\t\t -> lmao best_gap = " << best_gap << "\n";

	vector<long long> pivots;
	for (int j = 0; j < n; j++)
	{
		pivots.push_back(ST + j * best_gap);
	}
	pivots.back() = DR + 1;

	//for (auto& x : pivots)
	//{
	//	cout << x << " ";
	//}
	//cout << "\n";

	vector<pair<long long, long long>> intel(n - 1);
	for (int i = 0; i < n - 1; i++)
	{
		if (pivots[i] > pivots[i + 1] - 1)
		{
			intel[i] = { -1, -1 };
			continue;
		}
		MinMax(pivots[i], pivots[i + 1] - 1, &intel[i].first, &intel[i].second);
		//cout << i<<" : "<<intel[i].first << " " << intel[i].second << "\n";
	}
	for (int i = 0; i < n - 2; i++)
	{
		if (intel[i].second == -1)
		{
			continue;
		}
		int j = i + 1;
		while (j < n - 1 && intel[j].first == -1)
		{
			j++;
		}
		if (j < n - 1)
		{
			assert(intel[j].first != -1);
			best_gap = max(best_gap, intel[j].first - intel[i].second);
		}
	}

	return best_gap;
}

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