WarpSpeed's blog

Help needed in achieving customized sorting of 2-Dimensional arrays
By WarpSpeed, history, 9 years ago, In English

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?

  • Vote: I like it
  • -4
  • Vote: I do not like it

Comments Comments (6)
| Write comment?
»
9 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply
  • »
    »
    9 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Is cin/cout slower than scanf/printf? Pardon me for being a little naive as I'm just transitioning from C to C++.

    → Reply
    • »
      »
      »
      9 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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.

      → Reply
»
9 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

You need something better than O(NlogN) ?

P.S : O(NlogN) should be fine for N<=10^6

→ Reply
»
9 years ago, # |
  Vote: I like it 0 Vote: I do not like it

You need something better than O(NlogN) ?

P.S : O(NlogN) should be fine for N <  = 106

→ Reply
»
9 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

You can do this by using pair or struct keyword in C++.

Using pair

Using struct

Problem related to this

→ Reply