I have gone through sorting of simple 2-D arrays. And there are ample ways to do this efficiently. But lately, I'm facing some issues in sorting 2-D arrays with the following conditions:
Suppose there's a 2-D array with 2 rows and n columns. (Here n can vary from 1 upto 10^6) . All the entries are integer entries with the upper bound being 2 * 10^9 . The task here is to sort the elements in the first row in ascending order, preferably ( although, ascending/descending doesn't make much of a difference anyway ) and the elements of second row should occupy their new positions corresponding to their previous row-1 elements ( irrespective of their relations among other row-2 elements ).
A sample:
Suppose the array is as follows:
5 6 4 8 7 3
4 9 5 1 0 2
Then after sorting the final array should become:
3 4 5 6 7 8
2 5 4 9 0 1
With the conditions of n's upper bound going as high as 10^6, trivial methods of sorting this serve useless and lead to TLE message. How can the aforementioned task be achieved in the most efficient manner?
A nlogn sorting shouldn't give TLE even with 10**6 elements. Maybe there's some other problem? How many test cases are there? Also make sure you are using scanf/printf instead of cin/cout
Is cin/cout slower than scanf/printf? Pardon me for being a little naive as I'm just transitioning from C to C++.
Yes it is. Please read this: http://mirror.codeforces.com/blog/entry/5217 I generally use cin/cout and it works fine but if the input size is large and includes number of the order more then 10**5 then it is always better to use scanf/printf.
In this problem, you should use pair<int, int> array and then sort it.
You need something better than O(NlogN) ?
P.S : O(NlogN) should be fine for
N<=10^6You need something better than O(NlogN) ?
P.S : O(NlogN) should be fine for N < = 106
You can do this by using pair or struct keyword in C++.
Using pair
Using struct
Problem related to this