#include "xylophone.h"
#include <iostream>
#include <vector>
using namespace std;
/*
13 queries to find pos(N)
1 query for pos(N)+1
For i = pos(N)+2 .. N:
query(i-1, i)
query(i-2, i)
Figure out i
Do the same for i = 1..pos(1)-2
For pos(1) < i < pos(N):
*/
void debug(int y)
{
cout << y << '\n';
}
void debug(string S)
{
cout << S << '\n';
}
void debug(string S, int a, int b)
{
cout << S << ' ' << a << ' ' << b << '\n';
}
// ----------------------------------------------------------------------------
int n;
int searchN(int a, int b)
{
// debug("searchN", a, b);
if(a == b) return a;
int m = (a+b)/2;
if(query(1, m) == n-1) return searchN(a, m);
else return searchN(m+1, b);
}
vector<int> pos(5001, 0);
vector<int> A(5001, 0);
bool occ(int a) //occupied?
{
return (a < 1) || (n < a) || (pos[a] != 0);
}
void assign(int p, int a)
{
pos[a] = p;
A[p] = a;
answer(p, a);
}
void solve(int N)
{
// debug(111);
n = N;
assign( searchN(2, N), N );
//after N
if(pos[N] < N)
{
assign(pos[N] + 1, N - query(pos[N], pos[N] + 1));
}
// debug(555);
for(int i = pos[N]+2; i <= N; i++)
{
// debug(i);
int X1 = query(i-1, i);
if(occ(A[i-1] + X1)) assign(i, A[i-1] - X1);
else if(occ(A[i-1] - X1)) assign(i, A[i-1] + X1);
else
{
int X2 = query(i-2, i);
if(X2 == abs(A[i-1] - A[i-2]))
{
if(A[i-2] < A[i-1])
{
//A[i-2] < A[i] < A[i-1]
assign(i, A[i-1] - X1);
}
else
{
//A[i-1] < A[i] < A[i-2]
assign(i, A[i-1] + X1);
}
}
else
{
if(A[i-2] < A[i-1] && X1 > X2)
{
//A[i] < A[i-2] < A[i-1]
assign(i, A[i-1] - X1);
}
else if(A[i-2] < A[i-1] && X1 < X2)
{
//A[i-2] < A[i-1] < A[i]
assign(i, A[i-1] + X1);
}
else if(A[i-1] < A[i-2] && X1 > X2)
{
//A[i-1] < A[i-2] < A[i]
assign(i, A[i-1] + X1);
}
else if(A[i-1] < A[i-2] && X1 < X2)
{
//A[i] < A[i-1] < A[i-2]
assign(i, A[i-1] - X1);
}
else if(A[i-1] < A[i-2] && X1 == X2)
{
assign(i, A[i-1] + X1);
}
else// if(A[i-1] > A[i-2] && X1 == X2)
{
assign(i, A[i-1] - X1);
}
}
}
}
assign(pos[N] - 1, N - query(pos[N] - 1, pos[N]));
for(int i = pos[N]-2; i >= 1; i--)
{
// debug("new i = ");
// debug(i);
int X1 = query(i, i+1);
if(occ(A[i+1] + X1)) assign(i, A[i+1] - X1);
else if(occ(A[i+1] - X1)) assign(i, A[i+1] + X1);
else
{
int X2 = query(i, i+2);
if(X2 == abs(A[i+1] - A[i+2]))
{
if(A[i+2] < A[i+1])
{
//A[i-2] < A[i] < A[i-1]
assign(i, A[i+1] - X1);
}
else
{
//A[i-1] < A[i] < A[i-2]
assign(i, A[i+1] + X1);
}
}
else
{
if(A[i+2] < A[i+1] && X1 > X2)
{
//A[i] < A[i-2] < A[i-1]
assign(i, A[i+1] - X1);
}
else if(A[i+2] < A[i+1] && X1 < X2)
{
//A[i-2] < A[i-1] < A[i]
assign(i, A[i+1] + X1);
}
else if(A[i+1] < A[i+2] && X1 > X2)
{
//A[i-1] < A[i-2] < A[i]
assign(i, A[i+1] + X1);
}
else if(A[i+1] < A[i+2] && X1 < X2)
{
//A[i] < A[i-1] < A[i-2]
assign(i, A[i+1] - X1);
}
else if(A[i+1] < A[i+2] && X1 == X2)
{
assign(i, A[i+1] + X1);
}
else// if(A[i-1] > A[i-2] && X1 == X2)
{
assign(i, A[i+1] - X1);
}
}
}
}
}
//----------------------------------------------------------------------
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
364 KB |
Output is correct |
2 |
Correct |
1 ms |
364 KB |
Output is correct |
3 |
Correct |
1 ms |
364 KB |
Output is correct |
4 |
Correct |
2 ms |
364 KB |
Output is correct |
5 |
Correct |
2 ms |
364 KB |
Output is correct |
6 |
Correct |
2 ms |
364 KB |
Output is correct |
7 |
Correct |
2 ms |
364 KB |
Output is correct |
8 |
Correct |
2 ms |
364 KB |
Output is correct |
9 |
Correct |
2 ms |
364 KB |
Output is correct |
10 |
Correct |
1 ms |
364 KB |
Output is correct |
11 |
Correct |
2 ms |
364 KB |
Output is correct |
12 |
Correct |
2 ms |
364 KB |
Output is correct |
13 |
Correct |
2 ms |
364 KB |
Output is correct |
14 |
Correct |
2 ms |
364 KB |
Output is correct |
15 |
Correct |
2 ms |
364 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
364 KB |
Output is correct |
2 |
Correct |
1 ms |
364 KB |
Output is correct |
3 |
Correct |
1 ms |
364 KB |
Output is correct |
4 |
Correct |
2 ms |
364 KB |
Output is correct |
5 |
Correct |
2 ms |
364 KB |
Output is correct |
6 |
Correct |
2 ms |
364 KB |
Output is correct |
7 |
Correct |
2 ms |
364 KB |
Output is correct |
8 |
Correct |
2 ms |
364 KB |
Output is correct |
9 |
Correct |
2 ms |
364 KB |
Output is correct |
10 |
Correct |
1 ms |
364 KB |
Output is correct |
11 |
Correct |
2 ms |
364 KB |
Output is correct |
12 |
Correct |
2 ms |
364 KB |
Output is correct |
13 |
Correct |
2 ms |
364 KB |
Output is correct |
14 |
Correct |
2 ms |
364 KB |
Output is correct |
15 |
Correct |
2 ms |
364 KB |
Output is correct |
16 |
Correct |
4 ms |
364 KB |
Output is correct |
17 |
Correct |
9 ms |
364 KB |
Output is correct |
18 |
Correct |
10 ms |
364 KB |
Output is correct |
19 |
Correct |
13 ms |
384 KB |
Output is correct |
20 |
Correct |
18 ms |
364 KB |
Output is correct |
21 |
Correct |
11 ms |
364 KB |
Output is correct |
22 |
Correct |
14 ms |
364 KB |
Output is correct |
23 |
Correct |
10 ms |
364 KB |
Output is correct |
24 |
Correct |
9 ms |
364 KB |
Output is correct |
25 |
Correct |
9 ms |
364 KB |
Output is correct |
26 |
Correct |
13 ms |
364 KB |
Output is correct |
27 |
Correct |
18 ms |
364 KB |
Output is correct |
28 |
Correct |
16 ms |
364 KB |
Output is correct |
29 |
Correct |
17 ms |
364 KB |
Output is correct |
30 |
Correct |
14 ms |
364 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
364 KB |
Output is correct |
2 |
Correct |
1 ms |
364 KB |
Output is correct |
3 |
Correct |
1 ms |
364 KB |
Output is correct |
4 |
Correct |
2 ms |
364 KB |
Output is correct |
5 |
Correct |
2 ms |
364 KB |
Output is correct |
6 |
Correct |
2 ms |
364 KB |
Output is correct |
7 |
Correct |
2 ms |
364 KB |
Output is correct |
8 |
Correct |
2 ms |
364 KB |
Output is correct |
9 |
Correct |
2 ms |
364 KB |
Output is correct |
10 |
Correct |
1 ms |
364 KB |
Output is correct |
11 |
Correct |
2 ms |
364 KB |
Output is correct |
12 |
Correct |
2 ms |
364 KB |
Output is correct |
13 |
Correct |
2 ms |
364 KB |
Output is correct |
14 |
Correct |
2 ms |
364 KB |
Output is correct |
15 |
Correct |
2 ms |
364 KB |
Output is correct |
16 |
Correct |
4 ms |
364 KB |
Output is correct |
17 |
Correct |
9 ms |
364 KB |
Output is correct |
18 |
Correct |
10 ms |
364 KB |
Output is correct |
19 |
Correct |
13 ms |
384 KB |
Output is correct |
20 |
Correct |
18 ms |
364 KB |
Output is correct |
21 |
Correct |
11 ms |
364 KB |
Output is correct |
22 |
Correct |
14 ms |
364 KB |
Output is correct |
23 |
Correct |
10 ms |
364 KB |
Output is correct |
24 |
Correct |
9 ms |
364 KB |
Output is correct |
25 |
Correct |
9 ms |
364 KB |
Output is correct |
26 |
Correct |
13 ms |
364 KB |
Output is correct |
27 |
Correct |
18 ms |
364 KB |
Output is correct |
28 |
Correct |
16 ms |
364 KB |
Output is correct |
29 |
Correct |
17 ms |
364 KB |
Output is correct |
30 |
Correct |
14 ms |
364 KB |
Output is correct |
31 |
Correct |
25 ms |
364 KB |
Output is correct |
32 |
Correct |
40 ms |
364 KB |
Output is correct |
33 |
Correct |
51 ms |
364 KB |
Output is correct |
34 |
Correct |
36 ms |
364 KB |
Output is correct |
35 |
Correct |
75 ms |
364 KB |
Output is correct |
36 |
Correct |
43 ms |
364 KB |
Output is correct |
37 |
Correct |
34 ms |
364 KB |
Output is correct |
38 |
Correct |
62 ms |
364 KB |
Output is correct |
39 |
Correct |
35 ms |
364 KB |
Output is correct |
40 |
Correct |
66 ms |
364 KB |
Output is correct |
41 |
Correct |
61 ms |
364 KB |
Output is correct |
42 |
Correct |
51 ms |
364 KB |
Output is correct |
43 |
Correct |
47 ms |
364 KB |
Output is correct |
44 |
Correct |
58 ms |
364 KB |
Output is correct |
45 |
Correct |
80 ms |
364 KB |
Output is correct |
46 |
Correct |
79 ms |
364 KB |
Output is correct |
47 |
Correct |
61 ms |
364 KB |
Output is correct |
48 |
Correct |
62 ms |
364 KB |
Output is correct |
49 |
Correct |
69 ms |
364 KB |
Output is correct |
50 |
Correct |
87 ms |
364 KB |
Output is correct |
51 |
Correct |
67 ms |
364 KB |
Output is correct |
52 |
Correct |
34 ms |
364 KB |
Output is correct |
53 |
Correct |
59 ms |
364 KB |
Output is correct |
54 |
Correct |
58 ms |
364 KB |
Output is correct |
55 |
Correct |
37 ms |
364 KB |
Output is correct |
56 |
Correct |
55 ms |
364 KB |
Output is correct |
57 |
Correct |
57 ms |
364 KB |
Output is correct |
58 |
Correct |
60 ms |
384 KB |
Output is correct |
59 |
Correct |
59 ms |
364 KB |
Output is correct |
60 |
Correct |
59 ms |
364 KB |
Output is correct |