Submission #992090

#	Time	Username	Problem	Language	Result	Execution time	Memory
992090		MladenP	Gap (APIO16_gap)	C++17	100 / 100	43 ms	3060 KiB

gap

#include "gap.h"
#include <algorithm>
#include <iostream> 

using namespace std;

const long long MIN = 0;
const long long MAX = 1'000'000'000'000'000'000;
long long findGap(int T, int N)
{
	if (T == 1) {
		long long mn, mx; 
		long long prev_mn, prev_mx;
		long long sol = 0;
		MinMax(MIN, MAX, &prev_mn, &prev_mx);
		for (int i = 3; i <= N; i+=2) {
			MinMax(prev_mn+1, prev_mx-1, &mn, &mx);
			sol = max(sol, prev_mx-mx);
			sol = max(sol, mn-prev_mn);
			prev_mn = mn;
			prev_mx = mx;
		}
		if (prev_mn != prev_mx) {
			sol = max(sol, prev_mx-prev_mn);
		}
		return sol;
	} else if (T == 2) {
		long long mn, mx;
		MinMax(MIN, MAX, &mn, &mx); // N+1
		long long diff = (mx-mn + N-2)/(N-1), sol = 0, prev_mx = mn, st = mn+1;
		while (st <= mx) {
			long long en = min(mx, st+diff), cur_mn, cur_mx;
			MinMax(st, en, &cur_mn, &cur_mx);
			if (cur_mn != -1) {
				sol = max(sol, cur_mn - prev_mx);
				prev_mx = cur_mx;
			}
			st = en+1;
		}
		return sol;
	}
}

Compilation message (stderr)

gap.cpp: In function 'long long int findGap(int, int)':
gap.cpp:42:1: warning: control reaches end of non-void function [-Wreturn-type]
   42 | }
      | ^

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