oj.uz

Submission #594262

# Submission time Handle Problem Language Result Execution time Memory
594262 2022-07-12T09:45:35 Z Vanilla Gap (APIO16_gap) C++17
30 / 100
 2000 ms 6944 KB 
#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 l = 0, mn = -1, mx = -1;
		while (s.size() != n) {
			auto it = s.lower_bound(l);
			int64 r = (it == s.end() ? 1e18: *it); 
			// cout << s.size() << "\n";
			while (l <= r && s.size() != n) {
				MinMax(l, r, &mn, &mx);
				if (mn == -1) break;
				// cout << mn << " " << mx << "\n";
				s.insert(mn);
				s.insert(mx);
				if (mn == mx) break;
				l = mn + 1;
				r = min((l + r) / 2, mx - 1);
			}
			l = *s.lower_bound(l + 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

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: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) {
      |          ~~~~~~~~~^~~~
gap.cpp:29:30: warning: comparison of integer expressions of different signedness: 'std::set<long long int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   29 |    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.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 208 KB Output is correct
2 Correct 0 ms 280 KB Output is correct
3 Correct 1 ms 208 KB Output is correct
4 Correct 0 ms 208 KB Output is correct
5 Correct 1 ms 208 KB Output is correct
6 Correct 0 ms 336 KB Output is correct
7 Correct 1 ms 208 KB Output is correct
8 Correct 0 ms 208 KB Output is correct
9 Correct 0 ms 208 KB Output is correct
10 Correct 0 ms 208 KB Output is correct
11 Correct 1 ms 336 KB Output is correct
12 Correct 1 ms 336 KB Output is correct
13 Correct 1 ms 336 KB Output is correct
14 Correct 1 ms 336 KB Output is correct
15 Correct 1 ms 336 KB Output is correct
16 Correct 13 ms 2044 KB Output is correct
17 Correct 15 ms 1988 KB Output is correct
18 Correct 14 ms 1960 KB Output is correct
19 Correct 16 ms 2000 KB Output is correct
20 Correct 11 ms 2076 KB Output is correct
21 Correct 56 ms 6944 KB Output is correct
22 Correct 60 ms 6932 KB Output is correct
23 Correct 65 ms 6928 KB Output is correct
24 Correct 58 ms 6828 KB Output is correct
25 Correct 55 ms 6852 KB Output is correct
26 Correct 55 ms 6944 KB Output is correct
27 Correct 54 ms 6944 KB Output is correct
28 Correct 55 ms 6900 KB Output is correct
29 Correct 68 ms 6908 KB Output is correct
30 Correct 53 ms 6868 KB Output is correct
31 Correct 0 ms 208 KB Output is correct
32 Correct 0 ms 208 KB Output is correct

Subtask #2
0 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 208 KB Output is correct
2 Execution timed out 3079 ms 208 KB Time limit exceeded
3 Execution timed out 3087 ms 208 KB Time limit exceeded
4 Execution timed out 3054 ms 208 KB Time limit exceeded
5 Execution timed out 3083 ms 208 KB Time limit exceeded
6 Execution timed out 3085 ms 208 KB Time limit exceeded
7 Execution timed out 3087 ms 208 KB Time limit exceeded
8 Execution timed out 3089 ms 208 KB Time limit exceeded
9 Execution timed out 3091 ms 208 KB Time limit exceeded
10 Execution timed out 3053 ms 208 KB Time limit exceeded
11 Execution timed out 3090 ms 208 KB Time limit exceeded
12 Execution timed out 3068 ms 336 KB Time limit exceeded
13 Execution timed out 3089 ms 208 KB Time limit exceeded
14 Execution timed out 3081 ms 208 KB Time limit exceeded
15 Execution timed out 3090 ms 336 KB Time limit exceeded
16 Execution timed out 3084 ms 428 KB Time limit exceeded
17 Execution timed out 3078 ms 504 KB Time limit exceeded
18 Execution timed out 3080 ms 464 KB Time limit exceeded
19 Execution timed out 3068 ms 464 KB Time limit exceeded
20 Execution timed out 3098 ms 464 KB Time limit exceeded
21 Execution timed out 3055 ms 996 KB Time limit exceeded
22 Execution timed out 3072 ms 1056 KB Time limit exceeded
23 Execution timed out 3067 ms 1060 KB Time limit exceeded
24 Execution timed out 3060 ms 992 KB Time limit exceeded
25 Execution timed out 3064 ms 976 KB Time limit exceeded
26 Execution timed out 3064 ms 1044 KB Time limit exceeded
27 Execution timed out 3058 ms 964 KB Time limit exceeded
28 Execution timed out 3071 ms 1100 KB Time limit exceeded
29 Execution timed out 3056 ms 976 KB Time limit exceeded
30 Execution timed out 3077 ms 988 KB Time limit exceeded
31 Partially correct 0 ms 336 KB Partially correct
32 Execution timed out 3074 ms 208 KB Time limit exceeded