Hello,↵
↵
I was doing this [problem](http://www.usaco.org/index.php?page=viewproblem2&cpid=623) and was getting TLE on the last two test cases.↵
↵
On a whim, I decided to replace my sort() functions with stable_sort(), and the solution passed.↵
↵
According to this [benchmark](https://stackoverflow.com/questions/810951/how-big-is-the-performance-gap-between-stdsort-and-stdstable-sort-in-practic), stable_sort uses less iterations overall in g++ 5.3.0 and clang++ 3.7.0 than sort on average.↵
↵
In the problem I sorted a vector<pair<int, pair<int,int>>>, which would take up to three comparisons each time. I considered this a possibility for the lower constant factor of stable_sort for this problem, but was not able to replicate the results.↵
↵
You can try to submit my [solution](https://pastebin.com/37m5cVGX) and it should AC. But if you replace "stable_sort" with "sort" it will TLE.↵
↵
Does anyone know which types of cases stable_sort can outperform sort?↵
↵
Edit: Programs are compiled with gcc/g++ 4.8.2 using the "-O2" optimization flag and "-lm" to access the math library, and also "-std=c++0x" to enable support for C++11.
↵
I was doing this [problem](http://www.usaco.org/index.php?page=viewproblem2&cpid=623) and was getting TLE on the last two test cases.↵
↵
On a whim, I decided to replace my sort() functions with stable_sort(), and the solution passed.↵
↵
According to this [benchmark](https://stackoverflow.com/questions/810951/how-big-is-the-performance-gap-between-stdsort-and-stdstable-sort-in-practic), stable_sort uses less iterations overall in g++ 5.3.0 and clang++ 3.7.0 than sort on average.↵
↵
In the problem I sorted a vector<pair<int, pair<int,int>>>, which would take up to three comparisons each time. I considered this a possibility for the lower constant factor of stable_sort for this problem, but was not able to replicate the results.↵
↵
You can try to submit my [solution](https://pastebin.com/37m5cVGX) and it should AC. But if you replace "stable_sort" with "sort" it will TLE.↵
↵
Does anyone know which types of cases stable_sort can outperform sort?↵
↵
Edit: Programs are compiled with gcc/g++ 4.8.2 using the "-O2" optimization flag and "-lm" to access the math library, and also "-std=c++0x" to enable support for C++11.
