| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 594255 |
2022-07-12T09:34:48 Z |
Vanilla |
Gap (APIO16_gap) |
C++17 |
|
2000 ms |
6948 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 (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
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);
| ~~~~~~~~~^~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
208 KB |
Output isn't correct |
| 2 |
Correct |
0 ms |
208 KB |
Output is correct |
| 3 |
Correct |
0 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 |
Incorrect |
0 ms |
208 KB |
Output isn't correct |
| 7 |
Incorrect |
0 ms |
208 KB |
Output isn't correct |
| 8 |
Incorrect |
0 ms |
336 KB |
Output isn't correct |
| 9 |
Incorrect |
0 ms |
208 KB |
Output isn't correct |
| 10 |
Correct |
1 ms |
208 KB |
Output is correct |
| 11 |
Incorrect |
1 ms |
336 KB |
Output isn't correct |
| 12 |
Incorrect |
1 ms |
336 KB |
Output isn't correct |
| 13 |
Incorrect |
2 ms |
336 KB |
Output isn't correct |
| 14 |
Incorrect |
1 ms |
336 KB |
Output isn't correct |
| 15 |
Incorrect |
2 ms |
336 KB |
Output isn't correct |
| 16 |
Incorrect |
14 ms |
2100 KB |
Output isn't correct |
| 17 |
Incorrect |
13 ms |
2048 KB |
Output isn't correct |
| 18 |
Incorrect |
13 ms |
2056 KB |
Output isn't correct |
| 19 |
Incorrect |
15 ms |
2068 KB |
Output isn't correct |
| 20 |
Correct |
12 ms |
2000 KB |
Output is correct |
| 21 |
Incorrect |
64 ms |
6920 KB |
Output isn't correct |
| 22 |
Incorrect |
61 ms |
6932 KB |
Output isn't correct |
| 23 |
Incorrect |
74 ms |
6944 KB |
Output isn't correct |
| 24 |
Incorrect |
57 ms |
6856 KB |
Output isn't correct |
| 25 |
Incorrect |
54 ms |
6884 KB |
Output isn't correct |
| 26 |
Incorrect |
62 ms |
6828 KB |
Output isn't correct |
| 27 |
Incorrect |
69 ms |
6944 KB |
Output isn't correct |
| 28 |
Incorrect |
56 ms |
6852 KB |
Output isn't correct |
| 29 |
Incorrect |
59 ms |
6920 KB |
Output isn't correct |
| 30 |
Correct |
53 ms |
6864 KB |
Output is correct |
| 31 |
Correct |
0 ms |
336 KB |
Output is correct |
| 32 |
Correct |
1 ms |
208 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
3073 ms |
208 KB |
Time limit exceeded |
| 2 |
Execution timed out |
3052 ms |
208 KB |
Time limit exceeded |
| 3 |
Execution timed out |
3069 ms |
208 KB |
Time limit exceeded |
| 4 |
Execution timed out |
3072 ms |
208 KB |
Time limit exceeded |
| 5 |
Partially correct |
0 ms |
208 KB |
Partially correct |
| 6 |
Execution timed out |
3076 ms |
208 KB |
Time limit exceeded |
| 7 |
Execution timed out |
3075 ms |
208 KB |
Time limit exceeded |
| 8 |
Execution timed out |
3076 ms |
208 KB |
Time limit exceeded |
| 9 |
Execution timed out |
3057 ms |
208 KB |
Time limit exceeded |
| 10 |
Execution timed out |
3047 ms |
208 KB |
Time limit exceeded |
| 11 |
Execution timed out |
3069 ms |
336 KB |
Time limit exceeded |
| 12 |
Execution timed out |
3064 ms |
336 KB |
Time limit exceeded |
| 13 |
Execution timed out |
3091 ms |
336 KB |
Time limit exceeded |
| 14 |
Execution timed out |
3095 ms |
336 KB |
Time limit exceeded |
| 15 |
Partially correct |
1 ms |
336 KB |
Partially correct |
| 16 |
Execution timed out |
3090 ms |
1360 KB |
Time limit exceeded |
| 17 |
Execution timed out |
3076 ms |
1268 KB |
Time limit exceeded |
| 18 |
Execution timed out |
3077 ms |
1320 KB |
Time limit exceeded |
| 19 |
Execution timed out |
3090 ms |
1396 KB |
Time limit exceeded |
| 20 |
Execution timed out |
3090 ms |
976 KB |
Time limit exceeded |
| 21 |
Execution timed out |
3071 ms |
4516 KB |
Time limit exceeded |
| 22 |
Execution timed out |
3071 ms |
4512 KB |
Time limit exceeded |
| 23 |
Execution timed out |
3036 ms |
4548 KB |
Time limit exceeded |
| 24 |
Execution timed out |
3051 ms |
4532 KB |
Time limit exceeded |
| 25 |
Partially correct |
90 ms |
6948 KB |
Partially correct |
| 26 |
Execution timed out |
3054 ms |
4536 KB |
Time limit exceeded |
| 27 |
Execution timed out |
3055 ms |
4576 KB |
Time limit exceeded |
| 28 |
Execution timed out |
3026 ms |
4544 KB |
Time limit exceeded |
| 29 |
Execution timed out |
3032 ms |
4516 KB |
Time limit exceeded |
| 30 |
Execution timed out |
3048 ms |
2916 KB |
Time limit exceeded |
| 31 |
Execution timed out |
3056 ms |
208 KB |
Time limit exceeded |
| 32 |
Partially correct |
1 ms |
208 KB |
Partially correct |
