#include "xylophone.h"
#include <bits/stdc++.h>
#define int long long
using namespace std;
static int A[5001];
static bool isLess[5001][5001];
static int queries[5001][5001];
// On a |a[i+1] - a[i]|, |a[i+2] - a[i+1]|, max(...)
// a[i] < a[i+2] < a[i+1] : z = x
// a[i+1] < a[i+2] < a[i] : z = x
//
// a[i+1] < a[i] < a[i+2] : z = y
// a[i+2] < a[i] < a[i+1] : z = y
// a[i+2] < a[i+1] < a[i] : z > x,y
// a[i] < a[i+1] < a[i+2] : z > x,y
void solve(signed N)
{
isLess[1][2] = true;
for (int i(1); i < N; ++i)
queries[i][i+1] = query(i,i+1);
for (int i(1); i < N-1; ++i)
queries[i][i+2] = query(i, i+2);
for (int i(1); i+2 <= N; ++i)
{
int x(queries[i][i+1]), y(queries[i+1][i+2]), z(queries[i][i+2]);
if (x == z)
{
if (isLess[i][i+1])
isLess[i][i+2] = true, isLess[i+2][i+1] = true;
else
isLess[i+2][i] = true, isLess[i+1][i+2] = true;
}
else if (z == y)
{
if (isLess[i][i+1])
isLess[i+2][i] = isLess[i+2][i+1] = true;
else
isLess[i+1][i+2] = isLess[i][i+2] = true;
}
else
{
if (isLess[i][i+1])
isLess[i][i+2] = isLess[i+1][i+2] = true;
else
isLess[i+2][i+1] = isLess[i+2][i] = true;
}
}
for (int flip(0); flip < 2; ++flip)
for (int posMin(1); posMin <= N; ++posMin)
{
vector<bool> seen(N+1, false);
A[posMin] = 1;
for (int i(posMin-1); i; --i)
{
if (isLess[i][i+1] ^ flip)
A[i] = A[i+1] - queries[i][i+1];
else
A[i] = A[i+1] + queries[i][i+1];
}
for (int i(posMin+1); i <= N; ++i)
{
if (isLess[i-1][i] ^ flip)
A[i] = A[i-1] + queries[i-1][i];
else
A[i] = A[i-1] - queries[i-1][i];
}
bool ok(true);
for (int i(1); ok and i <= N; ++i)
{
if (A[i] < 1 or A[i] > N or seen[A[i]] or (i == posMin and seen[N]))
ok = false;
else
seen[A[i]] = true;
}
if (ok)
{
for (int i(1); i <= N; ++i)
answer(i, A[i]);
return ;
}
}
assert(false);
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
364 KB |
Output is correct |
2 |
Correct |
1 ms |
364 KB |
Output is correct |
3 |
Correct |
1 ms |
620 KB |
Output is correct |
4 |
Correct |
3 ms |
1024 KB |
Output is correct |
5 |
Correct |
3 ms |
1132 KB |
Output is correct |
6 |
Correct |
3 ms |
1132 KB |
Output is correct |
7 |
Correct |
3 ms |
1004 KB |
Output is correct |
8 |
Correct |
2 ms |
1004 KB |
Output is correct |
9 |
Correct |
3 ms |
1132 KB |
Output is correct |
10 |
Correct |
4 ms |
1132 KB |
Output is correct |
11 |
Correct |
3 ms |
1132 KB |
Output is correct |
12 |
Correct |
3 ms |
1132 KB |
Output is correct |
13 |
Correct |
3 ms |
1004 KB |
Output is correct |
14 |
Correct |
2 ms |
1004 KB |
Output is correct |
15 |
Correct |
2 ms |
1132 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
364 KB |
Output is correct |
2 |
Correct |
1 ms |
364 KB |
Output is correct |
3 |
Correct |
1 ms |
620 KB |
Output is correct |
4 |
Correct |
3 ms |
1024 KB |
Output is correct |
5 |
Correct |
3 ms |
1132 KB |
Output is correct |
6 |
Correct |
3 ms |
1132 KB |
Output is correct |
7 |
Correct |
3 ms |
1004 KB |
Output is correct |
8 |
Correct |
2 ms |
1004 KB |
Output is correct |
9 |
Correct |
3 ms |
1132 KB |
Output is correct |
10 |
Correct |
4 ms |
1132 KB |
Output is correct |
11 |
Correct |
3 ms |
1132 KB |
Output is correct |
12 |
Correct |
3 ms |
1132 KB |
Output is correct |
13 |
Correct |
3 ms |
1004 KB |
Output is correct |
14 |
Correct |
2 ms |
1004 KB |
Output is correct |
15 |
Correct |
2 ms |
1132 KB |
Output is correct |
16 |
Correct |
6 ms |
2028 KB |
Output is correct |
17 |
Correct |
12 ms |
4076 KB |
Output is correct |
18 |
Correct |
23 ms |
6380 KB |
Output is correct |
19 |
Correct |
48 ms |
7660 KB |
Output is correct |
20 |
Correct |
54 ms |
8172 KB |
Output is correct |
21 |
Correct |
60 ms |
7632 KB |
Output is correct |
22 |
Correct |
30 ms |
7680 KB |
Output is correct |
23 |
Correct |
21 ms |
8428 KB |
Output is correct |
24 |
Correct |
49 ms |
8428 KB |
Output is correct |
25 |
Correct |
24 ms |
8428 KB |
Output is correct |
26 |
Correct |
30 ms |
8172 KB |
Output is correct |
27 |
Correct |
38 ms |
8300 KB |
Output is correct |
28 |
Correct |
27 ms |
7660 KB |
Output is correct |
29 |
Correct |
50 ms |
7660 KB |
Output is correct |
30 |
Correct |
26 ms |
7660 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
364 KB |
Output is correct |
2 |
Correct |
1 ms |
364 KB |
Output is correct |
3 |
Correct |
1 ms |
620 KB |
Output is correct |
4 |
Correct |
3 ms |
1024 KB |
Output is correct |
5 |
Correct |
3 ms |
1132 KB |
Output is correct |
6 |
Correct |
3 ms |
1132 KB |
Output is correct |
7 |
Correct |
3 ms |
1004 KB |
Output is correct |
8 |
Correct |
2 ms |
1004 KB |
Output is correct |
9 |
Correct |
3 ms |
1132 KB |
Output is correct |
10 |
Correct |
4 ms |
1132 KB |
Output is correct |
11 |
Correct |
3 ms |
1132 KB |
Output is correct |
12 |
Correct |
3 ms |
1132 KB |
Output is correct |
13 |
Correct |
3 ms |
1004 KB |
Output is correct |
14 |
Correct |
2 ms |
1004 KB |
Output is correct |
15 |
Correct |
2 ms |
1132 KB |
Output is correct |
16 |
Correct |
6 ms |
2028 KB |
Output is correct |
17 |
Correct |
12 ms |
4076 KB |
Output is correct |
18 |
Correct |
23 ms |
6380 KB |
Output is correct |
19 |
Correct |
48 ms |
7660 KB |
Output is correct |
20 |
Correct |
54 ms |
8172 KB |
Output is correct |
21 |
Correct |
60 ms |
7632 KB |
Output is correct |
22 |
Correct |
30 ms |
7680 KB |
Output is correct |
23 |
Correct |
21 ms |
8428 KB |
Output is correct |
24 |
Correct |
49 ms |
8428 KB |
Output is correct |
25 |
Correct |
24 ms |
8428 KB |
Output is correct |
26 |
Correct |
30 ms |
8172 KB |
Output is correct |
27 |
Correct |
38 ms |
8300 KB |
Output is correct |
28 |
Correct |
27 ms |
7660 KB |
Output is correct |
29 |
Correct |
50 ms |
7660 KB |
Output is correct |
30 |
Correct |
26 ms |
7660 KB |
Output is correct |
31 |
Correct |
86 ms |
16108 KB |
Output is correct |
32 |
Correct |
376 ms |
22972 KB |
Output is correct |
33 |
Correct |
275 ms |
32236 KB |
Output is correct |
34 |
Correct |
1036 ms |
36980 KB |
Output is correct |
35 |
Correct |
999 ms |
36816 KB |
Output is correct |
36 |
Correct |
115 ms |
40940 KB |
Output is correct |
37 |
Correct |
1425 ms |
40940 KB |
Output is correct |
38 |
Correct |
109 ms |
40940 KB |
Output is correct |
39 |
Correct |
380 ms |
40160 KB |
Output is correct |
40 |
Correct |
810 ms |
36844 KB |
Output is correct |
41 |
Correct |
931 ms |
36888 KB |
Output is correct |
42 |
Correct |
142 ms |
40940 KB |
Output is correct |
43 |
Correct |
752 ms |
41080 KB |
Output is correct |
44 |
Correct |
119 ms |
40940 KB |
Output is correct |
45 |
Correct |
141 ms |
39916 KB |
Output is correct |
46 |
Correct |
809 ms |
40172 KB |
Output is correct |
47 |
Correct |
116 ms |
40044 KB |
Output is correct |
48 |
Correct |
831 ms |
40044 KB |
Output is correct |
49 |
Correct |
414 ms |
40044 KB |
Output is correct |
50 |
Correct |
1043 ms |
40052 KB |
Output is correct |
51 |
Correct |
110 ms |
36972 KB |
Output is correct |
52 |
Correct |
538 ms |
36972 KB |
Output is correct |
53 |
Correct |
956 ms |
37004 KB |
Output is correct |
54 |
Correct |
159 ms |
37004 KB |
Output is correct |
55 |
Correct |
789 ms |
36972 KB |
Output is correct |
56 |
Correct |
907 ms |
37100 KB |
Output is correct |
57 |
Correct |
228 ms |
36972 KB |
Output is correct |
58 |
Correct |
1278 ms |
36972 KB |
Output is correct |
59 |
Correct |
891 ms |
37080 KB |
Output is correct |
60 |
Correct |
358 ms |
36972 KB |
Output is correct |