| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 405778 |
2021-05-16T22:00:28 Z |
gevacrt |
Gap (APIO16_gap) |
C++17 |
|
68 ms |
1880 KB |
#include<bits/stdc++.h>
#include "gap.h"
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
typedef vector<ll> vi;
typedef pair<int, int> ii;
typedef vector<ii> vii;
typedef vector<vi> vvi;
typedef vector<vii> vvii;
#define INF INT_MAX
#define MOD 1000000007
#define all(x) x.begin(), x.end()
ll solve1(int N){
vi A(N); ll L = 0, R = 1e18;
for(int l = 0, r = N-1; l <= r; l++, r--){
MinMax(L, R, &A[l], &A[r]);
L = A[l]+1, R = A[r]-1;
assert(A[l] != -1 and A[r] != -1);
}
ll ans = 0;
for(int x = 0; x < N-1; x++)
ans = max(ans, A[x+1]-A[x]);
return ans;
}
ll solve2(int N){
ll L, R; MinMax(0, 1e18, &L, &R);
ll D = (R-L+N-2)/(N-1);
for(ll K = L+1; K < R; ){
ll mn, mx; MinMax(K, K+D-1, &mn, &mx);
if(mx != -1){
K = mx+1; continue;
}
for(ll i = 2; ; i++){
MinMax(K, K+i*D-1, &mn, &mx);
if(mn == -1) continue;
D = mn-K+1; K = mx+1;
break;
}
}
return D;
}
ll findGap(int T, int N){
if(T == 1) return solve1(N);
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 |
2 ms |
328 KB |
Output is correct |
| 12 |
Correct |
2 ms |
512 KB |
Output is correct |
| 13 |
Correct |
2 ms |
328 KB |
Output is correct |
| 14 |
Correct |
2 ms |
328 KB |
Output is correct |
| 15 |
Correct |
1 ms |
328 KB |
Output is correct |
| 16 |
Correct |
15 ms |
652 KB |
Output is correct |
| 17 |
Correct |
18 ms |
628 KB |
Output is correct |
| 18 |
Correct |
18 ms |
712 KB |
Output is correct |
| 19 |
Correct |
19 ms |
712 KB |
Output is correct |
| 20 |
Correct |
11 ms |
584 KB |
Output is correct |
| 21 |
Correct |
45 ms |
1804 KB |
Output is correct |
| 22 |
Correct |
53 ms |
1776 KB |
Output is correct |
| 23 |
Correct |
63 ms |
1856 KB |
Output is correct |
| 24 |
Correct |
56 ms |
1824 KB |
Output is correct |
| 25 |
Correct |
41 ms |
1756 KB |
Output is correct |
| 26 |
Correct |
49 ms |
1864 KB |
Output is correct |
| 27 |
Correct |
43 ms |
1756 KB |
Output is correct |
| 28 |
Correct |
68 ms |
1820 KB |
Output is correct |
| 29 |
Correct |
54 ms |
1828 KB |
Output is correct |
| 30 |
Correct |
38 ms |
1880 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 |
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 |
2 ms |
200 KB |
Output is correct |
| 12 |
Correct |
2 ms |
328 KB |
Output is correct |
| 13 |
Correct |
2 ms |
328 KB |
Output is correct |
| 14 |
Correct |
2 ms |
328 KB |
Output is correct |
| 15 |
Correct |
2 ms |
328 KB |
Output is correct |
| 16 |
Correct |
16 ms |
456 KB |
Output is correct |
| 17 |
Correct |
15 ms |
456 KB |
Output is correct |
| 18 |
Correct |
8 ms |
440 KB |
Output is correct |
| 19 |
Correct |
12 ms |
440 KB |
Output is correct |
| 20 |
Correct |
8 ms |
456 KB |
Output is correct |
| 21 |
Correct |
36 ms |
1048 KB |
Output is correct |
| 22 |
Correct |
35 ms |
1008 KB |
Output is correct |
| 23 |
Correct |
28 ms |
1048 KB |
Output is correct |
| 24 |
Correct |
29 ms |
1068 KB |
Output is correct |
| 25 |
Correct |
56 ms |
980 KB |
Output is correct |
| 26 |
Correct |
31 ms |
960 KB |
Output is correct |
| 27 |
Correct |
36 ms |
1088 KB |
Output is correct |
| 28 |
Correct |
36 ms |
1048 KB |
Output is correct |
| 29 |
Correct |
29 ms |
1028 KB |
Output is correct |
| 30 |
Correct |
24 ms |
1096 KB |
Output is correct |
| 31 |
Correct |
1 ms |
200 KB |
Output is correct |
| 32 |
Correct |
1 ms |
200 KB |
Output is correct |
