please give any hint how to solve this problem.
i now that we should use binary searching of height but how write dijkstra with 2 edge-parameters ?

Mine is O( log(MaxH) * N^4 )

In my solution I had to solve following interesting subproblem.

Given an array. There is somewhere a unique cutpoint in this array. We don't know where, but we can check, if x is a cutpoint in O(1). We have to find this cutpoint, split array in two parts and do the same recursively on both parts. We need to do it faster than in O(n^2).

Solution:
For a segment (l, r) check for cutpoints in following order: l, r, l+1, r-1, l+2, r-2, ...

Let's use pref_m[i][x], pref_le[i][x], suff_m[i][x], suff_le[i][x] where:
pref_m[i][x] - on [0;i) elements > x are in decreasing order;
pref_le[i][x] - on [0;i) elements <= x are in increasing order;
suff_m[i][x] - on [i;n) elements > x are in increasing order;
suff_le[i][x] - on [i;n) elements <= x are in decreasing order.

There is inc-dec-solution if and only if there exists some pos and val such that pref_m[pos][val], pref_le[pos][val], suff_m[pos][val] and suff_le[pos][val] are all true.

In order not to get ML you need to remove either positions or values from these arrays. It's your call to chose

11 may yield 1 twice via deletion

Test case is mentioned in other topic

10 10 10 10
1
1 0 10

Answer is 10

1)
4 4
1 2 9 15
1 4 0 8
2 3 20 30
3 1 31 0
1 4 9 30

->
4
1 3 4 2

2)
2 3
1 2 0 5
1 1 110 80
1 1 90 0
1 2 100 6

->
3
2 3 1

3)
3 6
1 2 50 55
2 1 55 40
1 2 0 1
1 3 41 80
3 2 80 12
2 1 15 0
1 2 49 7

->
6
1 2 4 5 6 3

After so many calculation and math I have solved the problem.....
Here we can have two worst cases...

Case 1:
having all the right shoes first.so here needed time is 2*b and we have now all the left shoes remaining...so total time is 2*b+40...

Case 2:
we may have 39 right shoes so time needed here is (39*2=78)...then we have only one right foot left but we may encounter all the left shoes and here needed time is 40+2*(a-40)....> 40 for the first 40 shoes and 2*(a-40) is for the remaining shoes as they needed to be thrown away...then we have the only one right foot left and it need 1 second...
so total time = 78+40+2*(a-40)+1 = 119+2*a-80 = 2*a-39

ans=max(Case 1,Case 2)


Edited by author 22.02.2020 03:07

Please, extend the limit for the size of submitted solution at least to 128 Kb. It is too hard to compress huge difficult solutions in 64 Kb without code obfuscation. There are some problems in this site that can require big source code (not pre-generated array of answers, but really huge algorithmic approach, like Voronoy diagram in 1369 or Sokoban/Ships)

Forgot to check that cell above the start is empty when jumping

I send program with such procedure:

void moveNorth(double dist)
{
  w += dist / rEarth * 180 / pi;
  if (w > 91.0)
    n = (n - n) / n;
}

And got crash 15, but when i send

void moveNorth(double dist)
{
  w += dist / rEarth * 180 / pi;
}

i got accepted.

So, i think device can reach north pole with test 15 input data, but it's impossible.

-0.001
-0.002
0

my integer-based output omitted "-" sign in that case

The following test helped me:

Input:
17
84 47 44 99 60 43 14 91 8 39 26 15 41 70 90 41 72 48 20 59 3 68 15 21 78 95 5 22 60 61 88 43 59 84 94 19 26 7 61 85 97 86 51 89 55 40 29 78 39 100 89 41 19 3 62 97 98 18 70 9 79 57 51 37 92 96 55 17 55 67 54 3 52 4 92 59 44 20 36 34 72 24 27 90 79
88 38 28 57 7 36 35 16 38 24 7 34 30 76 88 97 29 90 100 32 33 58 27 5 46 61 76 69 87 65 99 26 3 26 34 61 13 69 76 51 92 83 36 73 10 23 69 38 64 69 21 49 78 100 53 23 12 28 92 50 44 42 27 98 20 60 59 32 28 34 82 71 68 17 96 77 91 64 66 7 84 87 55 62 86 59 84 49 86
27 98 29 69 24 27 88 83 37 19 63 22 53 85 90 21 80 18 64 44 84 70 79 22 76 40 59 34
24 7 71 2 4 51 70 27 29 9 61 65 80 23 87 84 8 28 4 87 45 67 82 80 88
61 53 15 100 11 100 75 69 70 77 24 73 98 50 1 59 63 18 38 85 4 73 92 83 76 31 79 95 64 59 34 24 63 49 76 26 100 2 94 70 30 18 42 80 19 94 38 81 11 27 18 14 99 61 48 26 91 27 72 55 37 6
30 99 6 57 24 5 11 18 26 92 87 19 71 57 13 60 38 23 38 55 89 88 15 36 66 58 62 37 64 98 42
45 97 99 54 72 56 64 41 81 55 27 100 78 36 64 37 73 86 27 79 26 14 45 62 79 54 75 16 17 25 9 62 73 60 67 44 15 30 85 47 36 63 98 13 50 61
2 22 99
28 52 24 93 49 37 72 2 12 39 19 36 99 32 8 10 98 3 24 79 39 23 14 54 20 27 3 81 80
77 79 7 80 2 99 28 39 22 30 2 12 100 89 11 31 48 20 80 50 96 58 41 18 23 94 37 1 48 69 80 76 47 38 56 1 89 83 91 10 12 44 22 11 32 84 93 79 55 24 80 50 81 20 19 4 65 56 56 65 76 36 40 75 73 95 75 61 30 17 23 93 60 44 56 43 79 48
73 33 72 52 35 4 24 53 59 40 60 15 4 36 2 96 10 74 42 36 87 71 4 9 64 15 4 19 57 34 18 29 66 41 32 52 45 55 5 55 47 16 69 50 3 70 97 64 96 39 99 34 9 54 42 24 68 97 94 24 30 12 4 47 4 36 99 48 90 55 55 36 70 75
38 25 45 86 88 92 24 39 25 85 92 18 60 60 66 54 35 47 17 39 93 20 26 43 20 15 49 74 3 71 48 92 95 44 29 82 35 53 20
11 89 12 80 48 23 45 53 57 91 69 47
36 89 72 30 8 39 79 33 93 49 80 36 95 24 64 76 10 68 96 73 56 59 52 56 81 49 8 89 91 29 88 78 17 59 8 76 49
38 8 41 38 39 76 32 62 40 7 24 59 54 96 15 12 47 22 44 47 81 85 38 9 72 15 77 30 22 4 79 11 63 71 48 2 99 79 15
90 38 38 48 43 33 62 7 32 35 50 78 16 86 67 76 57 82 5 39 55 8 17 66 71 39 65 72 37 96 86 26 33 76 74 27 8 87 33 91 74 35 21 89 20 87 16 77 68 20 15 23 28 83 40 50 73 4 73 10 99 58 87 83 85 60 10 93 99 94 35 72 28 55 12 48 42 27 76 61 99 42 35 78 24 74 27 96 30 99 57
80 8 44 15 93 55 24 37 53 17 71 76 97 78 39 96 71 18 71 31 16 12 66 93 87 91 71 34 72 69 91 52 76 86 66 20 40 41 56 45 9 79 72 5 56 11 100 26 80 70 8 47 33 73 39 71 16 9 5 87 29 47 38 56 84 55 76 23 95 31 19 4 61 43 8 68 5 60 93 84 29

Output:
G
1 67

is operations of int64(pascal) slower than long long(c++)?

Does anyone know some tests to overcome WA 2?

It's very strange but it seems that even long double precision doesn't enough for this problem. I had function get_x(polyline, y), that calculates x coordinate of polyline on coordinate y. I implemented it through binary searching and then calculating by formula, but that resulted in WA23. Then I made an optimisation: if polyline has integer point with coordinate y: (x, y), I instantly return x.

Edited by author 03.01.2024 20:12