Last active
May 9, 2020 07:03
-
-
Save Gowtham-369/12c5c3b6e200e79d7734208ccd28b764 to your computer and use it in GitHub Desktop.
IARCS OPC Judge Problems » Sorting Rows of Numbers
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
You will be given several lines of input where each line contains a sequence of positive integers. | |
Your task is to sort these lines in lexicographic order. | |
Lexicographic order is the order in which words are listed in the dictionary. | |
The ordering is determined by the left most element (in this case the left most integer on each line) | |
and if the left most elements are equal then by the second element from the left, | |
if the left most and the second element from the left are equal then by the third element from the left and so on. | |
For example, when the lines | |
14 38 11 89 | |
27 34 | |
27 12 34 | |
27 | |
92 2 3 1 | |
17 2 | |
are sorted in the lexicographic order we get | |
14 38 11 89 | |
17 2 | |
27 | |
27 12 34 | |
27 34 | |
92 2 3 1 | |
Input: | |
The first line of the input contains a single integer N indicating the number of lines of input. This is followed by N lines (lines 2 through N+1) each which consists of a sequence of positive integers followed by a single −1. (The −1 is there just as an end marker and is not to be used in the sorting). Every line contains at the most 50 numbers. | |
Output: | |
N lines each containing a sequence of integers. These N lines must be the lexicographically sorted presentation of the N input lines. | |
Constraints: | |
1≤N≤1000. | |
There are at the most 50 integers on each line. | |
Sample input: | |
6 | |
14 38 11 89 -1 | |
27 34 -1 | |
27 12 34 -1 | |
27 -1 | |
92 2 3 1 -1 | |
17 2 -1 | |
Sample output: | |
14 38 11 89 | |
17 2 | |
27 | |
27 12 34 | |
27 34 | |
92 2 3 1 |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
#include <bits/stdc++.h> | |
#define PB push_back | |
using namespace std; | |
typedef vector<int> vi; | |
typedef vector<vector<int>> vvi; | |
void swap(vi& a,vi& b){ | |
vi temp = b; | |
b = a; | |
a = temp; | |
} | |
bool mycomp(int a,int b){ | |
return a<b; | |
} | |
void lexicographic_order(vector<vector<int>>& mat){ | |
int n = mat.size(); | |
for(int i=0; i<n; i++){ | |
for(int j=0; j<n-1-i; j++){ | |
if(!lexicographical_compare(mat[j].begin(),mat[j].end(),mat[j+1].begin(),mat[j+1].end(),mycomp)) | |
swap(mat[j],mat[j+1]); | |
} | |
} | |
/* | |
//int m;//min column size between any two lists we comapre | |
//i is used to shift column wise from left | |
int i = 0; | |
for (int k = 0; k < n; k++) | |
{ | |
for (int j = 0; j < n - 1 - k; j++) | |
{ | |
if (i < min(mat[j].size(), mat[j + 1].size())) | |
if (mat[j][i] > mat[j + 1][i]) | |
swap(mat[j], mat[j + 1]); | |
} | |
} | |
i = 1; | |
while(i<50){ | |
for(int k=0; k<n; k++){ | |
for(int j=0; j<n-1-k; j++) | |
{ | |
if (i < min(mat[j].size(), mat[j+1].size()) && mat[j][i-1] == mat[j+1][i-1]) | |
if(mat[j][i] > mat[j+1][i]) | |
swap(mat[j],mat[j+1]); | |
} | |
} | |
i++; | |
} | |
*/ | |
} | |
int main(){ | |
int N;// no of lists | |
cin>>N; | |
vvi mat; | |
int a; | |
for(int i=0; i<N; i++){ | |
vi v; | |
cin>>a; | |
while(a != -1){ | |
v.PB(a); | |
cin>>a; | |
} | |
v.PB(-1);//used for comparing | |
mat.PB(v); | |
} | |
//Now sorting in lexicographic order | |
lexicographic_order(mat); | |
for(vi v : mat){ | |
for(int x : v){ | |
if(x == -1) | |
break; | |
cout<<x<<' '; | |
} | |
cout<<'\n'; | |
} | |
return 0; | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment