Submission #126594

#	Time	Username	Problem	Language	Result	Execution time	Memory
126594		jakob_nogler	Gap (APIO16_gap)	C++14	30 / 100	2071 ms	524292 KiB

gap

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

using namespace std;

typedef long long ll;
typedef vector<ll> vll;

const ll inf = 1e18;

ll findGap(int T, int N){
	ll lo, hi, t_lo, t_hi, ans = 1, cnt = 2;
	MinMax(0, inf, &lo, &hi);

	if(N == 2) return hi - lo;
	if(T == 1){
		while(lo < hi){
			t_lo = lo, t_hi = hi;
			if(cnt == N){
				ans = max(ans, hi - lo);
				break;
			}
			if(lo + 1 >= hi - 1) break;
			MinMax(lo + 1, hi - 1, &lo, &hi);
			ans = max(ans, t_hi - hi);
			ans = max(ans, lo - t_lo);
			cnt += 2;
		}

		return ans;
	}

	vll vec;
	ll amm = (hi - lo) / (N - 2);
	//cout << amm << endl;

	vec.push_back(lo);
	int id = lo + 1;
	while(true){
		MinMax(id, id + amm, &t_lo, &t_hi);
		//cout << id << " " << id + amm << " " << t_lo << " " << t_hi << endl;
		if(t_lo != - 1){
			vec.push_back(t_lo);
			vec.push_back(t_hi);
		}
		if(id + amm + 1 >= hi) break;
		id += amm + 1;
	}
	vec.push_back(hi);

	for(int i = 0; i < vec.size() - 1; i++)
		ans = max(ans, vec[i + 1] - vec[i]);
	return ans;
}

Compilation message (stderr)

gap.cpp: In function 'll findGap(int, int)':
gap.cpp:51:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i = 0; i < vec.size() - 1; i++)
                 ~~^~~~~~~~~~~~~~~~

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