#include "xylophone.h"
#include <bits/stdc++.h>
using namespace std;
const int MAX_N = 5000;
int v[MAX_N + 1], ans[MAX_N + 1][MAX_N + 1];
unordered_map<int, bool> used;
int q( int l, int r ) {
if ( ans[l][r] == -1 )
ans[l][r] = query( l, r );
return ans[l][r];
}
void solve( int n ) {
int l = 1, r = n;
while ( r - l > 1 ) {
int mid = (l + r) / 2;
if ( query( mid, n ) == n - 1 )
l = mid;
else
r = mid;
}
int p1 = l;
for ( int l = 1; l <= n; l++ ) {
for ( int r = l; r <= n; r++ )
ans[l][r] = -1;
}
v[p1] = 1;
used[1] = true;
v[p1 + 1] = 1 + q( p1, p1 + 1 );
used[v[p1 + 1]] = true;
if ( p1 > 1 )
v[p1 - 1] = 1 + q( p1 - 1, p1 );
used[v[p1 - 1]] = true;
for ( int i = p1 + 2; i <= n; i++ ) {
int x = q( i - 1, i );
if ( v[i - 1] - x < 1 || used[v[i - 1] - x] ) {
v[i] = v[i - 1] + x;
continue;
}
if ( v[i - 1] + x > n || used[v[i - 1] + x] ) {
v[i] = v[i - 1] - x;
continue;
}
if ( v[i - 2] < v[i - 1] ) {
if ( q( i - 2, i ) == q( i - 2, i - 1 ) )
v[i] = v[i - 1] - q( i - 1, i );
else if ( q( i - 2, i ) == q( i - 1, i ) )
v[i] = v[i - 1] - q( i - 1, i );
else
v[i] = v[i - 1] + q( i - 1, i );
} else {
if ( q( i - 2, i ) == q( i - 2, i - 1 ) )
v[i] = v[i - 1] + q( i - 1, i );
else if ( q( i - 2, i ) == q( i - 1, i ) )
v[i] = v[i - 1] + q( i - 1, i );
else
v[i] = v[i - 1] - q( i - 1, i );
}
used[v[i]] = true;
}
for ( int i = p1 - 2; i >= 1; i-- ) {
int x = q( i, i + 1 );
if ( v[i + 1] - x < 1 || used[v[i + 1] - x] ) {
v[i] = v[i + 1] + x;
continue;
}
if ( v[i + 1] + x > n || used[v[i + 1] + x] ) {
v[i] = v[i + 1] - x;
continue;
}
if ( v[i + 2] < v[i + 1] ) {
if ( q( i, i + 2 ) == q( i + 1, i + 2 ) )
v[i] = v[i + 1] - q( i, i + 1);
else if ( q( i, i + 2 ) == q( i, i + 1 ) )
v[i] = v[i + 1] - q( i, i + 1 );
else
v[i] = v[i + 1] + q( i, i + 1 );
} else {
if ( q( i, i + 2 ) == q( i + 1, i + 2 ) )
v[i] = v[i + 1] + q( i, i + 1 );
else if ( q( i, i + 2 ) == q( i, i + 1 ) )
v[i] = v[i + 1] + q( i, i + 1 );
else
v[i] = v[i + 1] - q( i, i + 1 );
}
used[v[i]] = true;
}
for ( int i = 1; i <= n; i++ )
answer( i, v[i] );
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
344 KB |
Output is correct |
2 |
Correct |
0 ms |
648 KB |
Output is correct |
3 |
Correct |
1 ms |
2496 KB |
Output is correct |
4 |
Correct |
1 ms |
2488 KB |
Output is correct |
5 |
Correct |
1 ms |
2492 KB |
Output is correct |
6 |
Correct |
1 ms |
2488 KB |
Output is correct |
7 |
Correct |
1 ms |
2488 KB |
Output is correct |
8 |
Correct |
1 ms |
2488 KB |
Output is correct |
9 |
Correct |
1 ms |
2488 KB |
Output is correct |
10 |
Correct |
1 ms |
2496 KB |
Output is correct |
11 |
Correct |
1 ms |
2492 KB |
Output is correct |
12 |
Correct |
1 ms |
2488 KB |
Output is correct |
13 |
Correct |
1 ms |
2496 KB |
Output is correct |
14 |
Correct |
1 ms |
2492 KB |
Output is correct |
15 |
Correct |
1 ms |
2656 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
344 KB |
Output is correct |
2 |
Correct |
0 ms |
648 KB |
Output is correct |
3 |
Correct |
1 ms |
2496 KB |
Output is correct |
4 |
Correct |
1 ms |
2488 KB |
Output is correct |
5 |
Correct |
1 ms |
2492 KB |
Output is correct |
6 |
Correct |
1 ms |
2488 KB |
Output is correct |
7 |
Correct |
1 ms |
2488 KB |
Output is correct |
8 |
Correct |
1 ms |
2488 KB |
Output is correct |
9 |
Correct |
1 ms |
2488 KB |
Output is correct |
10 |
Correct |
1 ms |
2496 KB |
Output is correct |
11 |
Correct |
1 ms |
2492 KB |
Output is correct |
12 |
Correct |
1 ms |
2488 KB |
Output is correct |
13 |
Correct |
1 ms |
2496 KB |
Output is correct |
14 |
Correct |
1 ms |
2492 KB |
Output is correct |
15 |
Correct |
1 ms |
2656 KB |
Output is correct |
16 |
Correct |
2 ms |
6592 KB |
Output is correct |
17 |
Correct |
4 ms |
11448 KB |
Output is correct |
18 |
Correct |
6 ms |
17444 KB |
Output is correct |
19 |
Correct |
10 ms |
21532 KB |
Output is correct |
20 |
Correct |
9 ms |
21948 KB |
Output is correct |
21 |
Correct |
8 ms |
21440 KB |
Output is correct |
22 |
Correct |
10 ms |
21432 KB |
Output is correct |
23 |
Correct |
8 ms |
21572 KB |
Output is correct |
24 |
Correct |
11 ms |
21180 KB |
Output is correct |
25 |
Correct |
8 ms |
21692 KB |
Output is correct |
26 |
Correct |
7 ms |
21692 KB |
Output is correct |
27 |
Correct |
11 ms |
21312 KB |
Output is correct |
28 |
Correct |
10 ms |
21968 KB |
Output is correct |
29 |
Correct |
8 ms |
21944 KB |
Output is correct |
30 |
Correct |
7 ms |
21688 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
344 KB |
Output is correct |
2 |
Correct |
0 ms |
648 KB |
Output is correct |
3 |
Correct |
1 ms |
2496 KB |
Output is correct |
4 |
Correct |
1 ms |
2488 KB |
Output is correct |
5 |
Correct |
1 ms |
2492 KB |
Output is correct |
6 |
Correct |
1 ms |
2488 KB |
Output is correct |
7 |
Correct |
1 ms |
2488 KB |
Output is correct |
8 |
Correct |
1 ms |
2488 KB |
Output is correct |
9 |
Correct |
1 ms |
2488 KB |
Output is correct |
10 |
Correct |
1 ms |
2496 KB |
Output is correct |
11 |
Correct |
1 ms |
2492 KB |
Output is correct |
12 |
Correct |
1 ms |
2488 KB |
Output is correct |
13 |
Correct |
1 ms |
2496 KB |
Output is correct |
14 |
Correct |
1 ms |
2492 KB |
Output is correct |
15 |
Correct |
1 ms |
2656 KB |
Output is correct |
16 |
Correct |
2 ms |
6592 KB |
Output is correct |
17 |
Correct |
4 ms |
11448 KB |
Output is correct |
18 |
Correct |
6 ms |
17444 KB |
Output is correct |
19 |
Correct |
10 ms |
21532 KB |
Output is correct |
20 |
Correct |
9 ms |
21948 KB |
Output is correct |
21 |
Correct |
8 ms |
21440 KB |
Output is correct |
22 |
Correct |
10 ms |
21432 KB |
Output is correct |
23 |
Correct |
8 ms |
21572 KB |
Output is correct |
24 |
Correct |
11 ms |
21180 KB |
Output is correct |
25 |
Correct |
8 ms |
21692 KB |
Output is correct |
26 |
Correct |
7 ms |
21692 KB |
Output is correct |
27 |
Correct |
11 ms |
21312 KB |
Output is correct |
28 |
Correct |
10 ms |
21968 KB |
Output is correct |
29 |
Correct |
8 ms |
21944 KB |
Output is correct |
30 |
Correct |
7 ms |
21688 KB |
Output is correct |
31 |
Correct |
16 ms |
44212 KB |
Output is correct |
32 |
Correct |
31 ms |
62884 KB |
Output is correct |
33 |
Correct |
37 ms |
87616 KB |
Output is correct |
34 |
Correct |
49 ms |
98432 KB |
Output is correct |
35 |
Correct |
44 ms |
98300 KB |
Output is correct |
36 |
Correct |
38 ms |
97720 KB |
Output is correct |
37 |
Correct |
35 ms |
98240 KB |
Output is correct |
38 |
Correct |
35 ms |
98200 KB |
Output is correct |
39 |
Correct |
55 ms |
97976 KB |
Output is correct |
40 |
Correct |
46 ms |
98736 KB |
Output is correct |
41 |
Correct |
48 ms |
98140 KB |
Output is correct |
42 |
Correct |
37 ms |
98328 KB |
Output is correct |
43 |
Correct |
44 ms |
98528 KB |
Output is correct |
44 |
Correct |
38 ms |
97724 KB |
Output is correct |
45 |
Correct |
44 ms |
98960 KB |
Output is correct |
46 |
Correct |
48 ms |
98216 KB |
Output is correct |
47 |
Correct |
51 ms |
97976 KB |
Output is correct |
48 |
Correct |
46 ms |
98660 KB |
Output is correct |
49 |
Correct |
44 ms |
98460 KB |
Output is correct |
50 |
Correct |
47 ms |
97968 KB |
Output is correct |
51 |
Correct |
47 ms |
98356 KB |
Output is correct |
52 |
Correct |
46 ms |
98408 KB |
Output is correct |
53 |
Correct |
38 ms |
97996 KB |
Output is correct |
54 |
Correct |
47 ms |
97980 KB |
Output is correct |
55 |
Correct |
53 ms |
98080 KB |
Output is correct |
56 |
Correct |
45 ms |
98264 KB |
Output is correct |
57 |
Correct |
53 ms |
97720 KB |
Output is correct |
58 |
Correct |
42 ms |
98440 KB |
Output is correct |
59 |
Correct |
44 ms |
98080 KB |
Output is correct |
60 |
Correct |
45 ms |
97892 KB |
Output is correct |