Solution UVA: 612 - DNA Sorting

 

Last Submissions
Problem	Verdict	Lang	Time	Best	Rank	Submit Time
| discuss612 - DNA Sorting	Accepted	C++11	0.080	0.000	1036	4 mins ago

Problem: 612

Suggest:

- Function (f) is the number of inversions in the sequence

- Ez solve if you know data struct (dnas) and create function (comp) to compare (let see my code to know it) 

#include<bits/stdc++.h>

#define N 1000111

using namespace std;

int t, n, m;

struct dnas{

    int f, i;

    string dna;

};

dnas a[N];

string s;

int f(string s){

    int cnt= 0;

    for(int i=0; s[i+1]; i++)

        for(int j=i+1; s[j]; j++)

            if (s[i] > s[j]) cnt++;

    return cnt;

}

int comp(dnas tt, dnas ff){

    if (tt.f < ff.f)

        return true;

    if (tt.f == ff.f)

        return tt.i < ff.i;

    return false;

}

int main(){

    ios::sync_with_stdio(false); cin.tie(nullptr);

    cin >> t;

    while(t--){

        cin >> m >> n;

        for(int i=1; i<=n; i++){

            cin >> s;

           

            dnas x;

            x.f = f(s);

            x.i = i;

            x.dna = s;

           

            a[i]= x;

        }

        sort(a+1, a+1+n, comp);

        for(int i=1; i<=n; i++) cout<<a[i].dna<<"\n";

        if (t) cout<<"\n";  

    }

}