Warning: spoilers. Don't read if you have not solved problem.
------------------------------------------------------------











Well, I can't prove that there always exists path with such length, but I can prove that every path has at least such length.

Obviously, we need to prove that there is always at least (n + m + 1) diagonal moves.
Let cell be black if both it coordinates are not divisible by two and white otherwise.
There are (n+1)(m+1)/4 black squares.

Let f be amount of white cells we have visited plus amount of diagonal moves we have made.
We start our movement from some black point. When we start f is zero.

Assume we are now in black point.
Lemma
To reach another black points we need to increase f by at least 3.
Proof:
10101
00000
10X01
00000
10101
(X is our cell, 0's are while squares, 1 are black).
It's obvious, that if don't do diagonal moves at all, we need to visit at least 3 white squares.
If we do at least 2, then we visit at least one white square, 2 + 1 = 3.
If we do exactly 1, then if it is first move, then we can't leave white squares with second non-diagonal
move. If first move is non-diagonal, then second diagonal can't help. So in that case it's true too.
So we have proved lemma.

Now, f is amount of diagonal moves plus nm - (n+1)(m+1)/4. From the other side
f >= 3(n+1)(m+1)/4 because of lemma.
So (amount of diagonal moves) >= 4(n+1)(m+1)/4 - nm = n + m + 1.

Sorry for my bad English and possible bad explanation.















Spoilers End
--------------------

It was enough 5 tests for me. In first algo I used double and couldn't
fly over test 5. Based on my fail on 5 test I remade algo radically, excluded doubles
and got Ac 0.078. So, 5 tests are enough for debugging.

test 4
5
0 0 0 0 0
0 0 0 0 0
0 0 0 0 0
0 0 0 0 0
0 0 0 0 0

test 5
5
0 2 2 2 2
2 0 4 8 4
2 4 0 4 8
2 8 4 0 4
2 4 8 4 0

answers:

test 4
0 0
0 0
0 0
0 0
0 0

test 5
0 0
1 1
-1 1
-1 -1
1 -1

Edited by author 21.10.2011 00:44

WA#9 is because of integer overflow

It is actually a very tough problem when you're using a segments tree, so I do not think that using a SQRT-decomposition is a very good idea. For me the key was to implement the segments tree with iterative update procedure.

You are using frequency for occurrence greater than 1, why not use equal to 3 ?
Also B1 will contain repeated elements, instead try to use HashSet.

Same error for me. Don't know the problem man. :(

cin >> m;
while ( m != EOF )
{
//something
cin >> m;
}

They should be pairwise different.

想知道为什么ys是减1E-10，而xs是加1E-10！

想知道为什么ys是减1E-10，而xs是加1E-10！