It turns out, that there are possible two way to solve this problem (both M*N) in addition to naïve one (1400ms).
1.) Read all sites, then for each query point do find all the preliminary neighbours using float coordinates (it is almost two time faster in terms of membory bandwitdth, then if use double). This is a "float" sieve. Then for all sites passed "float" sieve perform similar "double" sieve. It get about 500ms (for me from 1.45s to 950ms). Test #16 is still hardest. Prefetch instructions in long runs gain up to 100ms.
First loop (precalc of squared float distances) can be unfolded 4 times by query points (vbroadcastss from fixed memory location works fast in loop, you should not occupy dedicated ymm register for these). Second loop, where squared distances compared against least distance (+ eps of course), found in previous loop, can be unfolded 4 times (you can occupy all 32 bit of some register using bit shift (ror, rol) after vmovmskps). I think it allow to better utilize branch prediction mechanism.
This approach can be beaten by simple test: cloud of sites in one corner in 10x10 square and cloud of query points in opposite aslo in 10x10 square both in general position (not matters much). Or wiser: query points placed on quarter of circle with center in one corner and radius of 20000, sites on another quarter of circle with center in the same corner and small radius or vice versa. Or even: two distant strait lines: one with query points and another with sites.
2.) You can solve the problem in single loop using just doubles with randomization. If your random numbers hit right sites, then you can probably make even fastest solution (but it is too improbably). I can't find counterexample for this randomized approach.

I am very interested in Progbeat's solution details. It seems (by memory consumed) he used approach very similar to mine. It would be great if we'll exchange our solutions somehow =).

I have WA#9 too. The program seems to be right. Who can help me?

Hi,

Very good solution! Just one note, it doesn't affect AC, but:

In D+=(i+N/i); if (i == N/i) you don't need to add both i and N/i, but just i.

In this case result of check(N) will be 100% equal to triviality(N) in all cases.

Oh no, that test is correct! I got AC.

Whoever gets Wrong Answer at 6th test, try to change your way of finding the power of two.

My solution got WA#6 when I calculated power of two this way:
power = ceil(log(x)/log(2));

Better calculate it by multiplying it.

5 10
answer : 2

It says: "in a row". It means that there can be any number of remixes of each song, the most important part it that the number in each row doesn't;t have to exceed a for 1st and b for 2nd

One would need Polya enumeration theorem to obtain an explicit formula though. Well, the theorem is a generalization of Burnside's anyway.