Submission #594265

#	Time	Username	Problem	Language	Result	Execution time	Memory
594265		Vanilla	Gap (APIO16_gap)	C++17	39.23 / 100	111 ms	7088 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);
	}
	else {
		set <int64> s;
		int64 last = -1;
		int64 l = 0, mn = -1, mx = -1;
		while (s.size() != n) {
			l = last + 1;
			auto it = s.lower_bound(l);
			int64 r = (it == s.end() ? 1e18: *it); 
			while (l <= r && s.size() != n) {
				MinMax(l, r, &mn, &mx);
				if (mn == -1) break;
				s.insert(mn);
				s.insert(mx);
				if (mn == mx) break;
				l = mn + 1;
				r = min((l + r) / 2, mx - 1);
			}
			last = *s.upper_bound(last);
		}
		for (int64 i: s) v.push_back(i);
	}
	assert(v.size() == n);
	for (int i = 1; i < n; i++){
		rs = max(rs, v[i] - v[i-1]);
	}
	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) {
      |          ~~~~~~~~~^~~~
gap.cpp:26:19: warning: comparison of integer expressions of different signedness: 'std::set<long long int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   26 |   while (s.size() != n) {
      |          ~~~~~~~~~^~~~
gap.cpp:30:30: warning: comparison of integer expressions of different signedness: 'std::set<long long int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   30 |    while (l <= r && s.size() != n) {
      |                     ~~~~~~~~~^~~~
In file included from /usr/include/c++/10/cassert:44,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:33,
                 from gap.cpp:1:
gap.cpp:43:18: warning: comparison of integer expressions of different signedness: 'std::vector<long long int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   43 |  assert(v.size() == n);
      |         ~~~~~~~~~^~~~

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