#include "xylophone.h"
#include <bits/stdc++.h>
using namespace std;
static int A[5000];
char has[5000];
void ans(int ind, int val) {
has[val] = 1;
A[ind] = val;
answer(ind + 1, val);
}
int n;
void sset(int i, int pr, int ppr) {
int p = query(min(i, pr) + 1, max(i, pr) + 1);
if (A[pr] - p > 0 && A[pr] + p <= n) {
int d = query(min(i, ppr) + 1, max(i, ppr) + 1);
if (max(max(A[pr] + p, A[pr]), A[ppr]) - min(min(A[pr] + p, A[pr]), A[ppr]) == d)
A[i] = A[pr] + p;
else
A[i] = A[pr] - p;
} else {
if (A[pr] - p <= 0)
A[i] = A[pr] + p;
else
A[i] = A[pr] - p;
}
ans(i, A[i]);
}
void solve(int N) {
n = N;
memset(has, 0, sizeof has);
int l = 1, r = N;
while (l < r) {
int mid = (l + r) >> 1;
int p = query(1, mid);
if (p == N - 1)
r = mid;
else
l = mid + 1;
}
l--;
ans(l, N);
if (l <= N / 2) {
for (int i = l - 1; i >= 0; i--)
sset(i, i + 1, i + 2);
for (int i = l + 1; i < N - 20; i++)
sset(i, i - 1, i - 2);
l = max(N - 20, l + 1);
int siz = N - l + 1;
int vals[N];
for (int i = l; i < N; i++)
vals[i] = query(i, i + 1);
for (int mask = 0; mask < (1 << siz); mask++) {
int cval = A[l - 1];
for (int j = l; j < N; j++) {
if (mask & (1 << (j - l)))
cval -= vals[j];
else
cval += vals[j];
if (has[cval] || cval <= 0 || cval > N) {
for (int k = j - 1; k >= l; k--)
has[A[k]] = 0;
goto nxt;
} else {
has[cval] = 1;
A[j] = cval;
}
}
for (int j = l; j < N; j++)
ans(j, A[j]);
return;
nxt:;
}
} else {
for (int i = l + 1; i < N; i++)
sset(i, i - 1, i - 2);
for (int i = l - 1; i >= 20; i--)
sset(i, i + 1, i + 2);
l = min(19, l - 1);
int siz = l + 1;
int vals[N];
for (int i = 0; i <= l; i++)
vals[i] = query(i + 1, i + 2);
for (int mask = 0; mask < (1 << siz); mask++) {
int cval = A[l + 1];
for (int j = l; j >= 0; j--) {
if (mask & (1 << (l - j)))
cval -= vals[j];
else
cval += vals[j];
if (has[cval] || cval > N || cval <= 0) {
for (int k = j + 1; k <= l; k++)
has[A[k]] = 0;
goto nxt2;
} else {
has[cval] = 1;
A[j] = cval;
}
}
for (int j = 0; j <= l; j++)
ans(j, A[j]);
return;
nxt2:;
}
}
}
Compilation message
xylophone.cpp: In function 'void solve(int)':
xylophone.cpp:94:7: warning: argument 1 range [18446744065119617024, 18446744073709551608] exceeds maximum object size 9223372036854775807 [-Walloc-size-larger-than=]
int vals[N];
^~~~
xylophone.cpp:94:7: note: in a call to built-in allocation function 'void* __builtin_alloca_with_align(long unsigned int, long unsigned int)'
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
384 KB |
Output is correct |
| 2 |
Correct |
2 ms |
384 KB |
Output is correct |
| 3 |
Correct |
12 ms |
256 KB |
Output is correct |
| 4 |
Correct |
7 ms |
256 KB |
Output is correct |
| 5 |
Correct |
6 ms |
384 KB |
Output is correct |
| 6 |
Correct |
8 ms |
256 KB |
Output is correct |
| 7 |
Correct |
8 ms |
256 KB |
Output is correct |
| 8 |
Correct |
15 ms |
256 KB |
Output is correct |
| 9 |
Correct |
22 ms |
384 KB |
Output is correct |
| 10 |
Correct |
8 ms |
256 KB |
Output is correct |
| 11 |
Correct |
6 ms |
304 KB |
Output is correct |
| 12 |
Correct |
10 ms |
256 KB |
Output is correct |
| 13 |
Correct |
4 ms |
256 KB |
Output is correct |
| 14 |
Correct |
5 ms |
256 KB |
Output is correct |
| 15 |
Correct |
7 ms |
256 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
384 KB |
Output is correct |
| 2 |
Correct |
2 ms |
384 KB |
Output is correct |
| 3 |
Correct |
12 ms |
256 KB |
Output is correct |
| 4 |
Correct |
7 ms |
256 KB |
Output is correct |
| 5 |
Correct |
6 ms |
384 KB |
Output is correct |
| 6 |
Correct |
8 ms |
256 KB |
Output is correct |
| 7 |
Correct |
8 ms |
256 KB |
Output is correct |
| 8 |
Correct |
15 ms |
256 KB |
Output is correct |
| 9 |
Correct |
22 ms |
384 KB |
Output is correct |
| 10 |
Correct |
8 ms |
256 KB |
Output is correct |
| 11 |
Correct |
6 ms |
304 KB |
Output is correct |
| 12 |
Correct |
10 ms |
256 KB |
Output is correct |
| 13 |
Correct |
4 ms |
256 KB |
Output is correct |
| 14 |
Correct |
5 ms |
256 KB |
Output is correct |
| 15 |
Correct |
7 ms |
256 KB |
Output is correct |
| 16 |
Correct |
12 ms |
384 KB |
Output is correct |
| 17 |
Correct |
16 ms |
384 KB |
Output is correct |
| 18 |
Correct |
15 ms |
256 KB |
Output is correct |
| 19 |
Correct |
22 ms |
256 KB |
Output is correct |
| 20 |
Correct |
24 ms |
256 KB |
Output is correct |
| 21 |
Correct |
15 ms |
384 KB |
Output is correct |
| 22 |
Correct |
19 ms |
256 KB |
Output is correct |
| 23 |
Correct |
19 ms |
336 KB |
Output is correct |
| 24 |
Correct |
17 ms |
340 KB |
Output is correct |
| 25 |
Correct |
11 ms |
344 KB |
Output is correct |
| 26 |
Correct |
23 ms |
384 KB |
Output is correct |
| 27 |
Correct |
24 ms |
256 KB |
Output is correct |
| 28 |
Correct |
21 ms |
256 KB |
Output is correct |
| 29 |
Correct |
13 ms |
256 KB |
Output is correct |
| 30 |
Correct |
21 ms |
384 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
384 KB |
Output is correct |
| 2 |
Correct |
2 ms |
384 KB |
Output is correct |
| 3 |
Correct |
12 ms |
256 KB |
Output is correct |
| 4 |
Correct |
7 ms |
256 KB |
Output is correct |
| 5 |
Correct |
6 ms |
384 KB |
Output is correct |
| 6 |
Correct |
8 ms |
256 KB |
Output is correct |
| 7 |
Correct |
8 ms |
256 KB |
Output is correct |
| 8 |
Correct |
15 ms |
256 KB |
Output is correct |
| 9 |
Correct |
22 ms |
384 KB |
Output is correct |
| 10 |
Correct |
8 ms |
256 KB |
Output is correct |
| 11 |
Correct |
6 ms |
304 KB |
Output is correct |
| 12 |
Correct |
10 ms |
256 KB |
Output is correct |
| 13 |
Correct |
4 ms |
256 KB |
Output is correct |
| 14 |
Correct |
5 ms |
256 KB |
Output is correct |
| 15 |
Correct |
7 ms |
256 KB |
Output is correct |
| 16 |
Correct |
12 ms |
384 KB |
Output is correct |
| 17 |
Correct |
16 ms |
384 KB |
Output is correct |
| 18 |
Correct |
15 ms |
256 KB |
Output is correct |
| 19 |
Correct |
22 ms |
256 KB |
Output is correct |
| 20 |
Correct |
24 ms |
256 KB |
Output is correct |
| 21 |
Correct |
15 ms |
384 KB |
Output is correct |
| 22 |
Correct |
19 ms |
256 KB |
Output is correct |
| 23 |
Correct |
19 ms |
336 KB |
Output is correct |
| 24 |
Correct |
17 ms |
340 KB |
Output is correct |
| 25 |
Correct |
11 ms |
344 KB |
Output is correct |
| 26 |
Correct |
23 ms |
384 KB |
Output is correct |
| 27 |
Correct |
24 ms |
256 KB |
Output is correct |
| 28 |
Correct |
21 ms |
256 KB |
Output is correct |
| 29 |
Correct |
13 ms |
256 KB |
Output is correct |
| 30 |
Correct |
21 ms |
384 KB |
Output is correct |
| 31 |
Correct |
56 ms |
420 KB |
Output is correct |
| 32 |
Correct |
42 ms |
256 KB |
Output is correct |
| 33 |
Correct |
45 ms |
424 KB |
Output is correct |
| 34 |
Correct |
79 ms |
464 KB |
Output is correct |
| 35 |
Correct |
72 ms |
256 KB |
Output is correct |
| 36 |
Correct |
85 ms |
324 KB |
Output is correct |
| 37 |
Correct |
60 ms |
336 KB |
Output is correct |
| 38 |
Correct |
64 ms |
336 KB |
Output is correct |
| 39 |
Correct |
50 ms |
336 KB |
Output is correct |
| 40 |
Correct |
67 ms |
344 KB |
Output is correct |
| 41 |
Correct |
84 ms |
332 KB |
Output is correct |
| 42 |
Correct |
100 ms |
468 KB |
Output is correct |
| 43 |
Correct |
38 ms |
424 KB |
Output is correct |
| 44 |
Correct |
32 ms |
376 KB |
Output is correct |
| 45 |
Correct |
79 ms |
256 KB |
Output is correct |
| 46 |
Correct |
49 ms |
408 KB |
Output is correct |
| 47 |
Correct |
67 ms |
416 KB |
Output is correct |
| 48 |
Correct |
73 ms |
336 KB |
Output is correct |
| 49 |
Correct |
82 ms |
256 KB |
Output is correct |
| 50 |
Correct |
74 ms |
376 KB |
Output is correct |
| 51 |
Correct |
75 ms |
256 KB |
Output is correct |
| 52 |
Correct |
56 ms |
256 KB |
Output is correct |
| 53 |
Correct |
67 ms |
468 KB |
Output is correct |
| 54 |
Correct |
50 ms |
340 KB |
Output is correct |
| 55 |
Correct |
71 ms |
328 KB |
Output is correct |
| 56 |
Correct |
39 ms |
388 KB |
Output is correct |
| 57 |
Correct |
68 ms |
376 KB |
Output is correct |
| 58 |
Correct |
30 ms |
336 KB |
Output is correct |
| 59 |
Correct |
61 ms |
504 KB |
Output is correct |
| 60 |
Correct |
35 ms |
336 KB |
Output is correct |
