Submission #735872

#	Time	Username	Problem	Language	Result	Execution time	Memory
735872		Abrar_Al_Samit	Gap (APIO16_gap)	C++17	38.81 / 100	50 ms	1876 KiB

gap

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

const long long INF = 1e18;


long long solve1(int N) {
	long long a[N+1];
	int l = 1, r = N;

	long long lef = 0, rit = INF;
	while(l<=r) {
		MinMax(lef, rit, &lef, &rit);
		if(l==r) {
			a[l] = lef;
			break;
		} else {
			a[l] = lef, a[r] = rit;
			++lef, --rit;
			++l, --r;
		}
	}

	long long best = 0;
	for(int i=2; i<=N; ++i) {
		best = max(best, a[i] - a[i-1]);
	}
	return best;
}
long long solve2(int N) {
	long long lef = 0;
	long long already = 1;
	bool very_first = true;

	long long absmn, absmx = INF;
	// if(N < 60) {
	// 	MinMax(0, INF, &absmn, &absmx);
	// 	lef = absmn + 1;
	// 	very_first = false;
	// }

	while(lef+already+1<=INF) {
		long long pw = already;
		while(1) {
			long long rit = min(INF, pw+lef-1);

			long long var1, var2;
			MinMax(lef, rit, &var1, &var2);
			if(var1==-1) {
				if(rit==INF) {
					return already;
				}
				pw *= 2;
			} else {
				if(!very_first) already = max(already, var1 - lef + 1), lef = var2 + 1;
				else lef = var1 + 1;
				break;
			}
		}
		very_first = false;
	}
	return already;
}
long long findGap(int T, int N) {
	if(T==1) return solve1(N);
	else return solve2(N);
}

Compilation message (stderr)

gap.cpp: In function 'long long int solve2(int)':
gap.cpp:36:12: warning: unused variable 'absmn' [-Wunused-variable]
   36 |  long long absmn, absmx = INF;
      |            ^~~~~
gap.cpp:36:19: warning: unused variable 'absmx' [-Wunused-variable]
   36 |  long long absmn, absmx = INF;
      |                   ^~~~~

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