fork download
copy 
  1.     #include<iostream>
  2.     #include<limits.h>
  3.     using namespace std;
  4.  
  5.     struct heapnode
  6.     {
  7.         int element;
  8.         int r;
  9.         int c;
  10.     };
  11.     class heap
  12.     {
  13.     public:
  14.         struct heapnode *harr;
  15.         int heapsize;
  16.         int capacity;
  17.  
  18.         heap(int n)
  19.         {
  20.             harr = new heapnode[n];
  21.             heapsize = 0;
  22.             capacity = n;
  23.         }
  24.         void minheapify(int i)
  25.         {
  26.             int smallest=i,lchild,rchild;
  27.             while(1)
  28.             {
  29.                 lchild = 2*i + 1;
  30.                 rchild = 2*i + 2;
  31.                 if(lchild<heapsize && harr[smallest].element > harr[lchild].element )
  32.                     smallest = lchild;
  33.                 if(rchild<heapsize && harr[smallest].element > harr[rchild].element)
  34.                     smallest = rchild;
  35.                 if(smallest!=i)
  36.                 {
  37.                     swap(harr[i],harr[smallest]);
  38.                     i = smallest;
  39.                 }
  40.                 else
  41.                     break;
  42.             }
  43.         }
  44.         void buildheap(int n)
  45.         {
  46.             heapsize = n;
  47.             for(int i=heapsize/2 -1;i>=0;i--)
  48.                 minheapify(i);
  49.         }
  50.     };
  51.     void printSortedMatrix(int **arr,int m,int n)
  52.     {
  53.         int k=m;
  54.         int i,j;
  55.         heap H(m);
  56.         struct heapnode hr;
  57.         int count =0;
  58.         while(1)
  59.         {
  60.             //cout<<count<<endl;
  61.             if(count < k-1)
  62.             {
  63.                 //cout<<count<<" "<<k<<endl;
  64.                 H.harr[count] = {arr[count][0],count,0};
  65.             }
  66.             else
  67.             {
  68.                 if(count==k-1)
  69.                 {
  70.                     H.harr[count] = {arr[count][0],count,0};
  71.                     H.buildheap(k);
  72.                 }
  73.                 if(H.harr[0].element==999)
  74.                     break;
  75.  
  76.                 cout<<H.harr[0].element<<" ";
  77.  
  78.                 hr = H.harr[0];
  79.                 if(hr.c==n)
  80.                     H.harr[0] = {999,0,0};
  81.                 else
  82.                     H.harr[0] = {arr[hr.r][hr.c+1],hr.r,hr.c+1};
  83.                 H.minheapify(0);
  84.             }
  85.             count++;
  86.         }
  87.         cout<<endl;
  88.     }
  89.  
  90.     int main()
  91.      {
  92.     	//code
  93.         int t,N,**arr,i,j,M;
  94.         cin>>t;
  95.         while(t--)
  96.         {
  97.             cin>>M;
  98.             N = M;
  99.             arr = new int*[M];
  100.             for(i=0;i<M;i++)
  101.                 arr[i] = new int[N];
  102.             for(i=0;i<M;i++)
  103.                 for(j=0;j<N;j++)
  104.                     cin>>arr[i][j];
  105.             printSortedMatrix(arr,M,N);
  106.         }
  107.     	return 0;
  108.     }
  109.  
Success #stdin #stdout 0s 16064KB
comments (?)
stdin
copy 
2
4
10 20 30 40 15 25 35 45 27 29 37 48 32 33 39 50
3
1 3 4 2 6 7 5 8 9
stdout
copy 
10 15 20 25 27 29 30 32 33 35 37 39 40 0 45 0 48 0 50 0 
1 2 3 4 0 5 6 7 0 8 9 0
https://ideone.com/Ctmo91
language:
C++ (gcc 8.3)
created:
8 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!