#include "shortcut_c.h"
#define N 1000000
#define INF 0x3f3f3f3f3f3f3f3f
long long min(long long a, long long b) { return a < b ? a : b; }
long long max(long long a, long long b) { return a > b ? a : b; }
unsigned int X = 12345;
int rand_() {
return (X *= 3) >> 1;
}
long long *aa;
#include <stdio.h>
void sort(int *ii, int l, int r) {
while (l < r) {
int i = l, j = l, k = r, i_ = ii[l + rand_() % (r - l)], tmp;
while (j < k)
if (aa[ii[j]] == aa[i_])
j++;
else if (aa[ii[j]] < aa[i_]) {
tmp = ii[i], ii[i] = ii[j], ii[j] = tmp;
i++, j++;
} else {
k--;
tmp = ii[j], ii[j] = ii[k], ii[k] = tmp;
}
sort(ii, l, i);
l = k;
}
}
long long find_shortcut(int n, int *xx_, int *dd, int c) {
static long long xx[N], yy[N], zz[N];
static int kk[N], ll[N];
int i, j, j1, j2, k, l, d, d1, d2, can;
long long x, y_, z_, lower, upper;
for (i = 1; i < n; i++)
xx[i] = xx[i - 1] + xx_[i - 1];
d1 = d2 = 0;
for (i = 0; i < n; i++) {
d = dd[i], x = xx[i], yy[i] = d - x, zz[i] = d + x;
if (d1 < d)
d2 = d1, d1 = d;
else if (d2 < d)
d2 = d;
kk[i] = ll[i] = i;
}
aa = yy, sort(kk, 0, n);
aa = zz, sort(ll, 0, n);
lower = d1 + d2 - 1, upper = xx[n - 1] + d1 + d2;
while (upper - lower > 1) {
long long d = (lower + upper) / 2, p, q, r, s;
p = q = r = s = INF, y_ = -INF, z_ = zz[ll[n - 1]];
for (k = 0; k < n; k++)
for (l = 0; l < n; l++)
if (yy[k] + zz[l] > d) {
/* dd[k] + dd[l] + |xx[k] - xx[i]| + c + |xx[l] - xx[j]| <= d
*
* max(xx[k] - xx[i], xx[i] - xx[k]) + max(xx[l] - xx[j], xx[j] - xx[l])
* <= d - (dd[k] + dd[l] + c)
*
* xx[k] - xx[i] + xx[l] - xx[j] <= d - (dd[k] + dd[l] + c)
* xx[k] - xx[i] + xx[j] - xx[l] <= d - (dd[k] + dd[l] + c)
* xx[i] - xx[k] + xx[l] - xx[j] <= d - (dd[k] + dd[l] + c)
* xx[i] - xx[k] + xx[j] - xx[l] <= d - (dd[k] + dd[l] + c)
*
* - xx[i] - xx[j] <= d - (dd[k] + dd[l] + c + xx[k] + xx[l])
* - xx[i] + xx[j] <= d - (dd[k] + dd[l] + c + xx[k] - xx[l])
* + xx[i] - xx[j] <= d - (dd[k] + dd[l] + c - xx[k] + xx[l])
* + xx[i] + xx[j] <= d - (dd[k] + dd[l] + c - xx[k] - xx[l]) */
p = min(p, d - (zz[k] + zz[l] + c));
q = min(q, d - (zz[k] + yy[l] + c));
r = min(r, d - (yy[k] + zz[l] + c));
s = min(s, d - (yy[k] + yy[l] + c));
}
can = 0;
for (i = 0, j1 = -1, j2 = n - 1; i < n; i++) {
x = xx[i];
while (j1 + 1 < n && - x + xx[j1 + 1] <= q)
j1++;
while (j2 >= 0 && + x + xx[j2] > s)
j2--;
j = min(j1, j2);
if (i < j && - x - xx[j] <= p && + x - xx[j] <= r) {
can = 1;
break;
}
}
if (can)
upper = d;
else
lower = d;
}
return upper;
}
Compilation message
shortcut.c: In function 'find_shortcut':
shortcut.c:42:19: warning: variable 'z_' set but not used [-Wunused-but-set-variable]
42 | long long x, y_, z_, lower, upper;
| ^~
shortcut.c:42:15: warning: variable 'y_' set but not used [-Wunused-but-set-variable]
42 | long long x, y_, z_, lower, upper;
| ^~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
204 KB |
n = 4, 80 is a correct answer |
| 2 |
Correct |
1 ms |
204 KB |
n = 9, 110 is a correct answer |
| 3 |
Correct |
1 ms |
204 KB |
n = 4, 21 is a correct answer |
| 4 |
Correct |
1 ms |
204 KB |
n = 3, 4 is a correct answer |
| 5 |
Incorrect |
1 ms |
204 KB |
n = 2, incorrect answer: jury 62 vs contestant 71 |
| 6 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
204 KB |
n = 4, 80 is a correct answer |
| 2 |
Correct |
1 ms |
204 KB |
n = 9, 110 is a correct answer |
| 3 |
Correct |
1 ms |
204 KB |
n = 4, 21 is a correct answer |
| 4 |
Correct |
1 ms |
204 KB |
n = 3, 4 is a correct answer |
| 5 |
Incorrect |
1 ms |
204 KB |
n = 2, incorrect answer: jury 62 vs contestant 71 |
| 6 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
204 KB |
n = 4, 80 is a correct answer |
| 2 |
Correct |
1 ms |
204 KB |
n = 9, 110 is a correct answer |
| 3 |
Correct |
1 ms |
204 KB |
n = 4, 21 is a correct answer |
| 4 |
Correct |
1 ms |
204 KB |
n = 3, 4 is a correct answer |
| 5 |
Incorrect |
1 ms |
204 KB |
n = 2, incorrect answer: jury 62 vs contestant 71 |
| 6 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
204 KB |
n = 4, 80 is a correct answer |
| 2 |
Correct |
1 ms |
204 KB |
n = 9, 110 is a correct answer |
| 3 |
Correct |
1 ms |
204 KB |
n = 4, 21 is a correct answer |
| 4 |
Correct |
1 ms |
204 KB |
n = 3, 4 is a correct answer |
| 5 |
Incorrect |
1 ms |
204 KB |
n = 2, incorrect answer: jury 62 vs contestant 71 |
| 6 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
204 KB |
n = 4, 80 is a correct answer |
| 2 |
Correct |
1 ms |
204 KB |
n = 9, 110 is a correct answer |
| 3 |
Correct |
1 ms |
204 KB |
n = 4, 21 is a correct answer |
| 4 |
Correct |
1 ms |
204 KB |
n = 3, 4 is a correct answer |
| 5 |
Incorrect |
1 ms |
204 KB |
n = 2, incorrect answer: jury 62 vs contestant 71 |
| 6 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
204 KB |
n = 4, 80 is a correct answer |
| 2 |
Correct |
1 ms |
204 KB |
n = 9, 110 is a correct answer |
| 3 |
Correct |
1 ms |
204 KB |
n = 4, 21 is a correct answer |
| 4 |
Correct |
1 ms |
204 KB |
n = 3, 4 is a correct answer |
| 5 |
Incorrect |
1 ms |
204 KB |
n = 2, incorrect answer: jury 62 vs contestant 71 |
| 6 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
204 KB |
n = 4, 80 is a correct answer |
| 2 |
Correct |
1 ms |
204 KB |
n = 9, 110 is a correct answer |
| 3 |
Correct |
1 ms |
204 KB |
n = 4, 21 is a correct answer |
| 4 |
Correct |
1 ms |
204 KB |
n = 3, 4 is a correct answer |
| 5 |
Incorrect |
1 ms |
204 KB |
n = 2, incorrect answer: jury 62 vs contestant 71 |
| 6 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
204 KB |
n = 4, 80 is a correct answer |
| 2 |
Correct |
1 ms |
204 KB |
n = 9, 110 is a correct answer |
| 3 |
Correct |
1 ms |
204 KB |
n = 4, 21 is a correct answer |
| 4 |
Correct |
1 ms |
204 KB |
n = 3, 4 is a correct answer |
| 5 |
Incorrect |
1 ms |
204 KB |
n = 2, incorrect answer: jury 62 vs contestant 71 |
| 6 |
Halted |
0 ms |
0 KB |
- |
