| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 406924 |
2021-05-18T08:31:48 Z |
SeDunion |
Gap (APIO16_gap) |
C++17 |
|
328 ms |
2740 KB |
#include "gap.h"
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
ll Answer(vector<ll>a) {
int N = a.size();
ll answer = 0;
for (int i = 0 ; i < N - 1 ; ++ i) answer = max(answer, a[i + 1] - a[i]);
return answer;
}
ll solve1(int N) {
ll L = -1, R = ll(1e18)+1;
vector<ll>a(N);
int l = 0, r = N - 1;
while (l <= r) {
MinMax(L+1, R-1, &L, &R);
a[l++] = L, a[r--] = R;
}
return Answer(a);
}
vector<ll>a;
void solve(ll L, ll R) {
if (L > R) return;
ll M = (L + R) / 2;
ll X;
MinMax(L, M, &L, &X);
if (L == -1 && X == -1) {
solve(M + 1, R);
return;
}
if (L == X) {
a.emplace_back(L);
solve(M + 1, R);
return;
}
a.emplace_back(L);
a.emplace_back(X);
solve(L + 1, X - 1);
solve(M + 1, R);
}
ll solve2(int N) {
ll L, R;
MinMax(0, ll(1e18), &L, &R);
a.emplace_back(L);
a.emplace_back(R);
solve(L + 1, R - 1);
sort(a.begin(), a.end());
assert((int)a.size() == N);
return Answer(a);
}
ll findGap(int T, int N) {
if (T == 1) {
return solve1(N);
} else {
return solve2(N);
}
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
200 KB |
Output is correct |
| 2 |
Correct |
1 ms |
200 KB |
Output is correct |
| 3 |
Correct |
1 ms |
200 KB |
Output is correct |
| 4 |
Correct |
1 ms |
200 KB |
Output is correct |
| 5 |
Correct |
1 ms |
200 KB |
Output is correct |
| 6 |
Correct |
1 ms |
200 KB |
Output is correct |
| 7 |
Correct |
1 ms |
200 KB |
Output is correct |
| 8 |
Correct |
1 ms |
200 KB |
Output is correct |
| 9 |
Correct |
1 ms |
200 KB |
Output is correct |
| 10 |
Correct |
1 ms |
200 KB |
Output is correct |
| 11 |
Correct |
1 ms |
328 KB |
Output is correct |
| 12 |
Correct |
1 ms |
328 KB |
Output is correct |
| 13 |
Correct |
1 ms |
328 KB |
Output is correct |
| 14 |
Correct |
1 ms |
328 KB |
Output is correct |
| 15 |
Correct |
1 ms |
328 KB |
Output is correct |
| 16 |
Correct |
11 ms |
848 KB |
Output is correct |
| 17 |
Correct |
11 ms |
832 KB |
Output is correct |
| 18 |
Correct |
11 ms |
840 KB |
Output is correct |
| 19 |
Correct |
15 ms |
840 KB |
Output is correct |
| 20 |
Correct |
9 ms |
840 KB |
Output is correct |
| 21 |
Correct |
44 ms |
2624 KB |
Output is correct |
| 22 |
Correct |
43 ms |
2592 KB |
Output is correct |
| 23 |
Correct |
44 ms |
2540 KB |
Output is correct |
| 24 |
Correct |
43 ms |
2584 KB |
Output is correct |
| 25 |
Correct |
41 ms |
2584 KB |
Output is correct |
| 26 |
Correct |
45 ms |
2652 KB |
Output is correct |
| 27 |
Correct |
52 ms |
2592 KB |
Output is correct |
| 28 |
Correct |
51 ms |
2616 KB |
Output is correct |
| 29 |
Correct |
42 ms |
2600 KB |
Output is correct |
| 30 |
Correct |
40 ms |
2624 KB |
Output is correct |
| 31 |
Correct |
1 ms |
200 KB |
Output is correct |
| 32 |
Correct |
1 ms |
200 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Partially correct |
1 ms |
200 KB |
Partially correct |
| 2 |
Partially correct |
1 ms |
200 KB |
Partially correct |
| 3 |
Partially correct |
1 ms |
200 KB |
Partially correct |
| 4 |
Partially correct |
1 ms |
200 KB |
Partially correct |
| 5 |
Partially correct |
1 ms |
200 KB |
Partially correct |
| 6 |
Partially correct |
1 ms |
200 KB |
Partially correct |
| 7 |
Partially correct |
1 ms |
200 KB |
Partially correct |
| 8 |
Partially correct |
1 ms |
200 KB |
Partially correct |
| 9 |
Partially correct |
1 ms |
200 KB |
Partially correct |
| 10 |
Partially correct |
1 ms |
200 KB |
Partially correct |
| 11 |
Partially correct |
6 ms |
328 KB |
Partially correct |
| 12 |
Partially correct |
4 ms |
328 KB |
Partially correct |
| 13 |
Partially correct |
4 ms |
276 KB |
Partially correct |
| 14 |
Partially correct |
4 ms |
348 KB |
Partially correct |
| 15 |
Partially correct |
3 ms |
328 KB |
Partially correct |
| 16 |
Partially correct |
70 ms |
956 KB |
Partially correct |
| 17 |
Partially correct |
87 ms |
1008 KB |
Partially correct |
| 18 |
Partially correct |
72 ms |
900 KB |
Partially correct |
| 19 |
Partially correct |
73 ms |
996 KB |
Partially correct |
| 20 |
Partially correct |
12 ms |
936 KB |
Partially correct |
| 21 |
Partially correct |
301 ms |
2704 KB |
Partially correct |
| 22 |
Partially correct |
296 ms |
2740 KB |
Partially correct |
| 23 |
Partially correct |
295 ms |
2736 KB |
Partially correct |
| 24 |
Partially correct |
328 ms |
2704 KB |
Partially correct |
| 25 |
Partially correct |
184 ms |
2700 KB |
Partially correct |
| 26 |
Partially correct |
304 ms |
2740 KB |
Partially correct |
| 27 |
Partially correct |
301 ms |
2736 KB |
Partially correct |
| 28 |
Partially correct |
299 ms |
2680 KB |
Partially correct |
| 29 |
Partially correct |
301 ms |
2712 KB |
Partially correct |
| 30 |
Partially correct |
52 ms |
2688 KB |
Partially correct |
| 31 |
Partially correct |
1 ms |
200 KB |
Partially correct |
| 32 |
Partially correct |
1 ms |
200 KB |
Partially correct |
