Submission #594255

#	Time	Username	Problem	Language	Result	Execution time	Memory
594255		Vanilla	Gap (APIO16_gap)	C++17	0 / 100	3095 ms	6948 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 (l <= r) {
			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, mn = -1, mx = -1;
		while (s.size() != n) {
			int64 l = last + 1;
			// cout << "> " << l << "\n";
			auto it = s.lower_bound(l);
			int64 r = (it == s.end() ? 1e18: *it); 
			while (l <= r) {
				int64 mid = (l + r) / 2;
				MinMax(l, mid, &mn, &mx);
				// cout << l << " " << r << " " << mn << " " << mx << "\n";
				if (mn == -1) break;
				s.insert(mn);
				s.insert(mx);
				if (mn == mx) break;
				r = min(mid - 1, mx - 1);
				l = mn + 1;
			}
			last = *s.lower_bound(last + 1);
		}
		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:25:19: warning: comparison of integer expressions of different signedness: 'std::set<long long int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   25 |   while (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:45:18: warning: comparison of integer expressions of different signedness: 'std::vector<long long int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   45 |  assert(v.size() == n);
      |         ~~~~~~~~~^~~~

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