Submission #594304

#	Time	Username	Problem	Language	Result	Execution time	Memory
594304		Vanilla	Gap (APIO16_gap)	C++17	30 / 100	70 ms	6944 KiB

gap

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

int64 findGap(int t, int n){
	vector <int64> v;
	int64 rs = -1;
	if (t == 1) {
		int64 l = 0, r = 1e18, mn = -1, mx = -1;
		set <int64> s;
		vector <int64> p1, p2;
		while (s.size() != n) {
			MinMax(l, r, &mn, &mx);
			if (mn == -1) break;
			s.insert(mn);
			s.insert(mx);
			l = mn + 1, r = mx - 1;
		}
		for (int64 i: s) v.push_back(i);
		for (int i = 1; i < n; i++){
			rs = max(rs, v[i] - v[i-1]);
		}
	}
	else {
		int64 mn = -1, mx = -1;
		MinMax(0, 1e18, &mn, &mx);
		if (n == 2) return mx - mn;
		int64 x = (mx - mn + n - 2) / (n - 1);
		int64 last = mn;
		for (int64 i = mn; i + x <= mx; i+=x + 1) {
			int64 nx, ny;
			MinMax(i, i + x, &nx, &ny);
			if (nx == -1) continue;
			rs = max(rs, nx - last);
			last = ny;
		}
	}
	return rs;
}

Compilation message (stderr)

gap.cpp: In function 'int64 findGap(int, int)':
gap.cpp:13:19: warning: comparison of integer expressions of different signedness: 'std::set<long long int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   13 |   while (s.size() != n) {
      |          ~~~~~~~~~^~~~

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