WarpSpeed's blog

By WarpSpeed, history, 4 years ago, ,

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?

• -4

 » 4 years ago, # |   0 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
•  » » 4 years ago, # ^ |   0 Is cin/cout slower than scanf/printf? Pardon me for being a little naive as I'm just transitioning from C to C++.
•  » » » 4 years ago, # ^ |   0 Yes it is. Please read this: http://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 array and then sort it.
 » 4 years ago, # | ← Rev. 2 →   0 You need something better than O(NlogN) ? P.S : O(NlogN) should be fine for N<=10^6
•  » » 4 years ago, # ^ | ← Rev. 2 →   0 I rely on the STL sort or the qsort in C when I have to sort a 2-D array normally, i.e, sort individual rows or columns. But here if I apply the STL sort to the row 1, then (since it being an in-place sort) how do I place the row-2 elements correspondingly?If possible, can you also post a code snippet showing the right way?
•  » » » 4 years ago, # ^ |   0
•  » » » » 4 years ago, # ^ |   0 Thanks a lot. :)
 » 4 years ago, # |   0 You need something better than O(NlogN) ? P.S : O(NlogN) should be fine for N <  = 106
 » 4 years ago, # | ← Rev. 2 →   0 You can do this by using pair or struct keyword in C++.Using pairUsing structProblem related to this
•  » » 4 years ago, # ^ |   0 Thanks a lot, friend! :) That was very helpful.