MULSORT  MultiSort
Members of the famous ENSI Competitive Programming Club try to gather a huge database of problem sets. They need to sort all the problems according to their difficulty levels. Each of the M club members takes N problems and brings back the sorted list. The score (difficulty level) is a real value evaluated as a combination of many criterions. Write a program that outputs the global sorted list of N*M problems.
Input
First line of input consists of an integer T denoting the number of test cases. Then T test cases follow. Each case begins with two lines containing two integers M and N (N*M<=10^6). Each of the M next lines contains N space separated real numbers (scores) in descending order. All the scores are guaranteed to be in [0, 10].
Output
A single line for each test case consisting of N*M space separeted problems. Each problem is represented by i,j where i is the input member position (from 1 to M) and j is the position in the original list (from 1 to N). Problems are sorted by score (descending order) then by member's position (ascending order) and finally by problem's position in the original member’s list (ascending order).
Input File is large. Use fast I/O methods.
Example
Input: 1 3 4 9.195 4.17 2.532 0.03 8.28 5.5 4 2.69 8.8320 7.9 2.18 0 Output: 1,1 3,1 2,1 3,2 2,2 1,2 2,3 2,4 1,3 3,3 1,4 3,4
hide comments
vineetjai:
20200905 09:21:54
AC in n*m*logm 

chaks03:
20180707 05:08:33
Getting NZEC again and again (java) even with bufferedreader. I am unable to verify the inputs. The test inputs work fine locally. 

prajjyadv0904:
20180628 18:21:56
O(n*m*logn) is also giving tle : ( 

prakash1108:
20180614 10:46:09
Last edit: 20180618 18:16:45 

tanya02_11:
20180613 07:34:19
can anyone give a hint to solve my answer is getting timel limit exceed


ryuuk:
20180602 21:41:17
@mehmetin, you will get TLE if your solution is in O(N*M*log(N*M)) 

mehmetin:
20180602 20:03:15
My previous AC code gets TLE, I think a rejudge should be made, if possible. 

nils75:
20180602 13:28:41
@nadstratosfer : I increased it a little. If I do more non intended solutions will be accepted. 

nadstratosfer:
20180601 20:17:48
Please increase TL so that PyPy solutions can pass. It's not even possible to just read a million lines in 0.3s (see http://www.spoj.com/ranks/INTEST/lang=PYPY2.4 ).


ryuuk:
20180601 14:39:16
nice problem :D 
Added by:  adminensi 
Date:  20180529 
Time limit:  1s 
Source limit:  50000B 
Memory limit:  1536MB 
Cluster:  Cube (Intel G860) 
Languages:  All 