For people who think that mergesort and quicksort will give TLE for this question, it wont. Maybe u guys are getting tle because of a slow i/o method. Here’s my implementation of mergesort for AC. CodeChef: Practical coding for everyone
Nope. quicksort won’t. Not mergesort as well, if implemented properly. I used the sort function from the algorithm library which uses the quicksort algorithm for large n and nope, it didn’t give TLE. Dont worry it’ll work!
Standard Sorting(C++) - 2.39 s
Merge Sort - 3.11 s
Heap Sort - 3.10 s
Count Sort - 2.33 s
Results posted by someone on comments of the same problem on SPOJ.
My bad Anyway can I see your implementation of Standard sort which was AC on Spoj? What’s the point of solving the question then if you solve with any sorting algorithm (n log n).
Nobody would have used bubble sort, i am sure! If u feel that someone has used bubble sort and still submitted successfully, please comment a link of the solution! Bubble sort can never solve this problem. You atleast require an O(nlogn) technique.