Div2 C test 59 is a stdlib qsort() killer!

Learned my lesson today: shuffle before using quicksort

My solution without shuffle: 28226684 (TLE 59)
My solution with shuffle: 28235814 (Accepted)

Not only me, other C (without plus-plus) user (rainboy) is also affected:

rainboy's solution without suffle: 28219544 (TLE59)
rainboy's solution with suffle: 28233646 (Accepted)

Then I search for source code for qsort() gnu implementation and found this: https://code.woboq.org/userspace/glibc/stdlib/qsort.c.html

It choose the pivot element using a median-of-three decision tree. After I read this: https://stackoverflow.com/questions/7559608/median-of-three-values-strategy the median of tree is pivot selection strategy to prevent worst case performance on easy to make case like "almost sorted data".

So I think it's not easy to make this qsort work in O(n²), but this test 59 prove that it's something common (although this is first time I encounter this problem after ~3.5 years experience in competitive programming).

How to make testcase that make this stdlib qsort() run in worst case O(n²)?

I trusted this function for years and now... he betrayed me :p

Div1 version: Few failed systest, few hack attempt (and no successful hack), and few active participant (391 active of 656 registered) :/ Fortunately the problem is not bad :)

It begin at Jan 21, not Jan 20. You almost give me a heart attack, I think I miss the round :p

RIP english, I assume you want the I/O files to make a gym contest, in that case you can find full I/O files here: https://www.dropbox.com/sh/bvnrwslazmr5ztc/AACZYKtzHq1mY4YrRQN-GFbDa?dl=0

Full Editorial: https://www.facebook.com/notes/facebook-hacker-cup/hacker-cup-2017-round-1-solutions/1599716033377625

your hash type is 32 bit, it means your hash value has 2^32 possible value, according to:

https://en.wikipedia.org/wiki/Birthday_attack and https://en.wikipedia.org/wiki/Birthday_problem

It says that if we have 10^6 object (pokemons) and hash value is 32 bit (2^32) the probability of at least 1 collision is over 99% no matter how good your hash function, but if we use 64 bit the probability of collision is far less than 1%

I'm curious if there are accepted user with 32-bit hash? I want to confirm wiki theorem :p

TAXIMAN

That's because people who failed systest get negative score instead of zero ;)

My solution: Angular sort, radial sweep, range query.
Complexity: O(n³log(n)).

Is there O(n³) solution or better exists?