#include <bits/stdc++.h>
#include "gap.h"
using namespace std;
vector<long long> arr;
long long part1(int N)
{
long long mn = -1, mx = 1e18 + 2;
arr.resize(N);
int i = 0, j = N-1;
while(i <= j)
{
long long a = mn+1, b = mx-1;
if(a > b)
break;
MinMax(a, b, &mn, &mx);
arr[i] = mn;
arr[j] = mx;
i++;
j--;
}
long long max_diff = 0;
for(int i = 0; i < N-1; i++)
max_diff = max(max_diff, arr[i+1] - arr[i]);
return max_diff;
}
int idx = 0;
void aux(long long l, long long r, long long step)
{
long long mn = -1, mx = 1e18 + 2;
int i = 1;
while(l + step * i - 1 < r)
{
MinMax(l + step * (i-1), l + step * i - 1, &mn, &mx);
if(mn != -1) {
if(step == 1) {
arr[idx] = mn;
idx++;
}
else
aux(l + step * (i-1), l + step * i - 1, step / 1e6);
}
i++;
}
}
long long part2(int N)
{
arr.resize(N);
aux(0, 1e18, 1e12);
long long max_diff = 0;
for(int i = 0; i < N-1; i++)
max_diff = max(max_diff, arr[i+1] - arr[i]);
return max_diff;
}
long long findGap(int T, int N)
{
if(T == 1)
return part1(N);
else
return part2(N);
}
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
0 ms |
344 KB |
Output is correct |
| 2 |
Correct |
0 ms |
344 KB |
Output is correct |
| 3 |
Correct |
0 ms |
344 KB |
Output is correct |
| 4 |
Correct |
0 ms |
344 KB |
Output is correct |
| 5 |
Correct |
0 ms |
344 KB |
Output is correct |
| 6 |
Correct |
0 ms |
344 KB |
Output is correct |
| 7 |
Correct |
0 ms |
344 KB |
Output is correct |
| 8 |
Correct |
0 ms |
344 KB |
Output is correct |
| 9 |
Correct |
0 ms |
344 KB |
Output is correct |
| 10 |
Correct |
0 ms |
344 KB |
Output is correct |
| 11 |
Correct |
1 ms |
344 KB |
Output is correct |
| 12 |
Correct |
1 ms |
344 KB |
Output is correct |
| 13 |
Correct |
1 ms |
344 KB |
Output is correct |
| 14 |
Correct |
1 ms |
344 KB |
Output is correct |
| 15 |
Correct |
1 ms |
344 KB |
Output is correct |
| 16 |
Correct |
7 ms |
660 KB |
Output is correct |
| 17 |
Correct |
8 ms |
600 KB |
Output is correct |
| 18 |
Correct |
7 ms |
692 KB |
Output is correct |
| 19 |
Correct |
7 ms |
856 KB |
Output is correct |
| 20 |
Correct |
5 ms |
660 KB |
Output is correct |
| 21 |
Correct |
27 ms |
1976 KB |
Output is correct |
| 22 |
Correct |
27 ms |
1880 KB |
Output is correct |
| 23 |
Correct |
26 ms |
1880 KB |
Output is correct |
| 24 |
Correct |
27 ms |
1880 KB |
Output is correct |
| 25 |
Correct |
23 ms |
1880 KB |
Output is correct |
| 26 |
Correct |
27 ms |
1880 KB |
Output is correct |
| 27 |
Correct |
26 ms |
1880 KB |
Output is correct |
| 28 |
Correct |
26 ms |
1880 KB |
Output is correct |
| 29 |
Correct |
27 ms |
1880 KB |
Output is correct |
| 30 |
Correct |
23 ms |
1880 KB |
Output is correct |
| 31 |
Incorrect |
0 ms |
344 KB |
Output isn't correct |
| 32 |
Correct |
0 ms |
344 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Partially correct |
52 ms |
344 KB |
Partially correct |
| 2 |
Partially correct |
651 ms |
344 KB |
Partially correct |
| 3 |
Partially correct |
637 ms |
344 KB |
Partially correct |
| 4 |
Partially correct |
690 ms |
344 KB |
Partially correct |
| 5 |
Partially correct |
363 ms |
432 KB |
Partially correct |
| 6 |
Execution timed out |
3043 ms |
344 KB |
Time limit exceeded |
| 7 |
Execution timed out |
3029 ms |
344 KB |
Time limit exceeded |
| 8 |
Execution timed out |
3056 ms |
344 KB |
Time limit exceeded |
| 9 |
Execution timed out |
3038 ms |
344 KB |
Time limit exceeded |
| 10 |
Partially correct |
109 ms |
344 KB |
Partially correct |
| 11 |
Execution timed out |
3026 ms |
344 KB |
Time limit exceeded |
| 12 |
Execution timed out |
3062 ms |
344 KB |
Time limit exceeded |
| 13 |
Execution timed out |
3039 ms |
344 KB |
Time limit exceeded |
| 14 |
Execution timed out |
3049 ms |
344 KB |
Time limit exceeded |
| 15 |
Execution timed out |
3069 ms |
344 KB |
Time limit exceeded |
| 16 |
Execution timed out |
3039 ms |
600 KB |
Time limit exceeded |
| 17 |
Execution timed out |
3029 ms |
600 KB |
Time limit exceeded |
| 18 |
Execution timed out |
3072 ms |
600 KB |
Time limit exceeded |
| 19 |
Execution timed out |
3072 ms |
600 KB |
Time limit exceeded |
| 20 |
Partially correct |
299 ms |
672 KB |
Partially correct |
| 21 |
Execution timed out |
3068 ms |
1880 KB |
Time limit exceeded |
| 22 |
Execution timed out |
3028 ms |
1880 KB |
Time limit exceeded |
| 23 |
Execution timed out |
3069 ms |
1880 KB |
Time limit exceeded |
| 24 |
Execution timed out |
3034 ms |
1880 KB |
Time limit exceeded |
| 25 |
Execution timed out |
3016 ms |
1880 KB |
Time limit exceeded |
| 26 |
Execution timed out |
3027 ms |
1880 KB |
Time limit exceeded |
| 27 |
Execution timed out |
3030 ms |
1880 KB |
Time limit exceeded |
| 28 |
Execution timed out |
3038 ms |
1880 KB |
Time limit exceeded |
| 29 |
Execution timed out |
3036 ms |
1880 KB |
Time limit exceeded |
| 30 |
Partially correct |
477 ms |
1880 KB |
Partially correct |
| 31 |
Execution timed out |
2302 ms |
428 KB |
Time limit exceeded |
| 32 |
Execution timed out |
2097 ms |
344 KB |
Time limit exceeded |
