Submission #586625

#	Time	Username	Problem	Language	Result	Execution time	Memory
586625		GioChkhaidze	Gap (APIO16_gap)	C++14	30 / 100	44 ms	3280 KiB

gap

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

#define ll long long
#define pb push_back

using namespace std;

const int Nn = 1e5 + 5;

ll a[Nn];

long long findGap(int T, int N) {
	ll ans = 0;
	if (T == 1) {
		ll Mn = -1, Mx = -1, l = 0, r = N - 1;
		MinMax(0ll, 1000000000000000000ll, &Mn, &Mx);
		a[l] = Mn, a[r] = Mx;
		while (l + 1 < r) {
			MinMax(a[l] + 1, a[r] - 1, &Mn, &Mx);
			if (Mn == -1 && Mx == -1) {
				break;
			}
			a[++l] = Mn;
			a[--r] = Mx;
		}
		for (int i = 1; i < N; ++i) {
			ans = max(ans, a[i] - a[i - 1]);
		}		
	}
		else
	if (T == 2) {
		vector < ll > s;
		ll Mn = -1, Mx = -1, l = 0, r = N - 1;
		MinMax(0ll, 1000000000000000000ll, &Mn, &Mx);
		int A = Mn, B = Mx;
		ll len = (Mx - Mn + 1) / N;
		s.pb(A);
		for (ll i = A; i < B; i += len) {
			Mn = i + 1, Mx = i + len;
			MinMax(0ll, 1000000000000000000ll, &Mn, &Mx);
			if (Mn == -1 && Mx == -1) continue;
			s.pb(Mn), s.pb(Mx);
		}
		s.pb(B);
		for (int i = 1; i < s.size(); ++i) {
			ans = max(ans, s[i] - s[i - 1]);
		} 
	}
	return ans;
}

Compilation message (stderr)

gap.cpp: In function 'long long int findGap(int, int)':
gap.cpp:46:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   46 |   for (int i = 1; i < s.size(); ++i) {
      |                   ~~^~~~~~~~~~
gap.cpp:34:24: warning: unused variable 'l' [-Wunused-variable]
   34 |   ll Mn = -1, Mx = -1, l = 0, r = N - 1;
      |                        ^
gap.cpp:34:31: warning: unused variable 'r' [-Wunused-variable]
   34 |   ll Mn = -1, Mx = -1, l = 0, r = N - 1;
      |                               ^

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