Submission #519634

#	Time	Username	Problem	Language	Result	Execution time	Memory
519634		aryan12	Gap (APIO16_gap)	C++17	100 / 100	59 ms	3172 KiB

gap

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

long long Solve1(long long N) {
	long long A[N];
	long long L = 0, R = N - 1;
	long long valL = 0, valR = 1e18;
	while(L <= R) {
		MinMax(valL, valR, &valL, &valR);
		A[L++] = valL;
		A[R--] = valR;
		valL++;
		valR--;
	}
	long long ans = 0;
	for(long long i = 1; i < N; i++) {
		ans = max(ans, A[i] - A[i - 1]);
	}
	return ans;
}

long long Solve2(long long N) {
	vector<long long> A;
	long long l, r;
	long long mn, mx;
	MinMax(0, 1e18, &mn, &mx);
	A.push_back(mn);
	A.push_back(mx);
	long long store_mx = mx - 1;
	long long len = (mx - mn + N - 2) / (N - 1);
	//cout << "\nlen = " << len << "\n";
	l = mn, r = mx;
	while(l < r) {
		l = mn + 1;
		r = min(mn + len, store_mx);
		MinMax(l, r, &mn, &mx);
		//cout << "l = " << l << ", r = " << r << ", mn = " << mn << ", mx = " << mx << "\n";
		if(mn == -1) {
			mn = r;
			if(r == store_mx) break;
			continue;
		}
		A.push_back(mn);
		A.push_back(mx);
		mn = r;
		if(r == store_mx) {
			break;
		}
	}
	sort(A.begin(), A.end());
	long long ans = 0;
	for(int i = 1; i < A.size(); i++) {
		ans = max(ans, A[i] - A[i - 1]);
	}
	return ans;
}

long long findGap(int T, int N)
{
	if(T == 1) return Solve1(N);
	return Solve2(N);
}

Compilation message (stderr)

gap.cpp: In function 'long long int Solve2(long long int)':
gap.cpp:53:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   53 |  for(int i = 1; i < A.size(); i++) {
      |                 ~~^~~~~~~~~~

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