| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 680582 |
2023-01-11T10:03:19 Z |
Alexandruabcde |
Gap (APIO16_gap) |
C++14 |
|
61 ms |
3196 KB |
#include <bits/stdc++.h>
#include "gap.h"
using namespace std;
constexpr long long INF = 1LL * 1e18;
constexpr int NMAX = 1e5 + 2;
long long ans = 0;
long long A[NMAX];
void Solve_Task_1(int N) {
long long st = 1, dr = INF;
long long *Min, *Max;
Min = A + 1;
Max = A + N;
for (int i = 2; i <= N; i += 2) {
MinMax(st, dr, Min, Max);
st = (*Min) + 1;
dr = (*Max) - 1;
Min++;
Max--;
}
if (N % 2 == 1) {
MinMax(st, dr, A + (N+1) / 2, A + (N+1)/2);
}
for (int i = 2; i <= N; ++ i )
ans = max(ans, A[i] - A[i-1]);
}
void Solve_Task_2(int N) {
ans = 0;
long long st = 0, dr = INF;
long long *Min, *Max;
Min = A + 1;
Max = A + 2;
MinMax(st, dr, Min, Max);
long long average_diff = (A[2] - A[1]) / (N - 1);
dr = A[2];
st = A[1];
vector <long long> values;
while (st <= dr) {
MinMax(st, st + average_diff, Min, Max);
if (A[1] != -1) values.push_back(A[1]);
if (A[2] != -1) values.push_back(A[2]);
st += average_diff + 1;
}
for (int i = 1; i < values.size(); ++ i )
ans = max(ans, values[i] - values[i-1]);
}
long long findGap(int T, int N)
{
ans = 0;
if (T == 1) Solve_Task_1(N);
else Solve_Task_2(N);
return ans;
}
Compilation message
gap.cpp: In function 'void Solve_Task_2(int)':
gap.cpp:57:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
57 | for (int i = 1; i < values.size(); ++ i )
| ~~^~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
208 KB |
Output is 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 |
0 ms |
208 KB |
Output is correct |
| 6 |
Correct |
0 ms |
208 KB |
Output is correct |
| 7 |
Correct |
0 ms |
208 KB |
Output is correct |
| 8 |
Correct |
0 ms |
208 KB |
Output is correct |
| 9 |
Correct |
1 ms |
208 KB |
Output is correct |
| 10 |
Correct |
0 ms |
208 KB |
Output is correct |
| 11 |
Correct |
2 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 |
9 ms |
620 KB |
Output is correct |
| 17 |
Correct |
11 ms |
676 KB |
Output is correct |
| 18 |
Correct |
12 ms |
604 KB |
Output is correct |
| 19 |
Correct |
12 ms |
692 KB |
Output is correct |
| 20 |
Correct |
9 ms |
664 KB |
Output is correct |
| 21 |
Correct |
42 ms |
1832 KB |
Output is correct |
| 22 |
Correct |
48 ms |
1856 KB |
Output is correct |
| 23 |
Correct |
39 ms |
1864 KB |
Output is correct |
| 24 |
Correct |
48 ms |
1848 KB |
Output is correct |
| 25 |
Correct |
31 ms |
1856 KB |
Output is correct |
| 26 |
Correct |
35 ms |
1860 KB |
Output is correct |
| 27 |
Correct |
53 ms |
1828 KB |
Output is correct |
| 28 |
Correct |
36 ms |
1956 KB |
Output is correct |
| 29 |
Correct |
41 ms |
1784 KB |
Output is correct |
| 30 |
Correct |
34 ms |
1776 KB |
Output is correct |
| 31 |
Correct |
0 ms |
208 KB |
Output is correct |
| 32 |
Correct |
0 ms |
208 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
208 KB |
Output is 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 |
Correct |
1 ms |
208 KB |
Output is correct |
| 7 |
Correct |
0 ms |
208 KB |
Output is correct |
| 8 |
Correct |
1 ms |
208 KB |
Output is correct |
| 9 |
Correct |
1 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 |
384 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 |
14 ms |
848 KB |
Output is correct |
| 17 |
Correct |
12 ms |
848 KB |
Output is correct |
| 18 |
Correct |
13 ms |
816 KB |
Output is correct |
| 19 |
Correct |
12 ms |
944 KB |
Output is correct |
| 20 |
Correct |
8 ms |
536 KB |
Output is correct |
| 21 |
Correct |
55 ms |
2244 KB |
Output is correct |
| 22 |
Correct |
48 ms |
2252 KB |
Output is correct |
| 23 |
Correct |
58 ms |
2240 KB |
Output is correct |
| 24 |
Correct |
60 ms |
2208 KB |
Output is correct |
| 25 |
Correct |
57 ms |
3196 KB |
Output is correct |
| 26 |
Correct |
61 ms |
2256 KB |
Output is correct |
| 27 |
Correct |
51 ms |
2168 KB |
Output is correct |
| 28 |
Correct |
52 ms |
2160 KB |
Output is correct |
| 29 |
Correct |
61 ms |
2204 KB |
Output is correct |
| 30 |
Correct |
32 ms |
1480 KB |
Output is correct |
| 31 |
Correct |
1 ms |
208 KB |
Output is correct |
| 32 |
Correct |
0 ms |
208 KB |
Output is correct |
