# PBinfo #4712 – aperm – Rezolvare C++

Sursa: Codul lui Andrei
Limbaj: C++
Autor rezolvare: Darius

## Enunț

Se consideră o matrice cu n linii și p coloane. Fiecare linie a matricei este o permutare a mulțimii {1, 2, ..., p}.

Cerința
Să se ordoneze lexicografic liniile matricei.

Date de intrare
Fișierul de intrare aperm.in conține pe prima linie numerele n și p separate prin spațiu. Pe următoarele n linii se găsesc câte p numere naturale separate prin spațiu, fiecare linie fiind o permutare a mulțimii {1, 2, ..., p}.

Date de ieșire
Fișierul de ieșire aperm.out va conține n linii. A i-a linie va conține un singur număr natural reprezentând numărul de ordine al liniei din matrice care se află pe poziția i după ordonarea lexicografică a liniilor.

Restricții și precizări

3 ≤ n ≤ 50.000
2 ≤ p ≤ 16
Dacă sunt linii identice în permutare, aceste linii se vor afișa în ordinea crescătoare a indicilor.

Exemplu:
aperm.in

5 4
1 3 4 2
4 1 2 3
1 3 2 4
4 1 2 3
3 2 4 1
aperm.out

3
1
5
2
4
Explicație
Cea mai mică permutare din punct de vedere lexicografic este cea de pe linia a treia. Urmează prima linie, apoi a cincea. A doua linie și a patra linie din matrice sunt cele mai mari lexicografic și identice, deci se afișează mai întâi 2, apoi 4.

## Cod sursă C++

```cpp
/*
    Complexitate O(n x p x p + n log n)
*/
#include <algorithm>
#include <cstdio>
#define Nmax 50005
#define inFile "aperm.in"
#define outFile "aperm.out"
using namespace std;
struct permut
{
    long long val;
    int ind;
};
long long f[20];
permut a[Nmax];
int n, p, t[20];
void Factoriale()
{
    int i;
    f[0] = f[1] = 1;
    for (i = 2; i <= 16; ++i)
        f[i] = f[i - 1] * i;
}
long long Ordine(int t[])
{
    int i, j;
    long long x;
    x = 1;
    for (i = 1; i <= p; ++i)
    {
        x = x + (t[i] - 1) * f[p - i];
        for (j = i + 1; j <= p; ++j)
            if (t[j] > t[i]) t[j]--;
    }
    return x;
}
void Citire()
{
    int i, j;
    freopen(inFile, "r", stdin);
    scanf("%d %d", &n, &p);
    for (i = 1; i <= n; ++i)
    {
        for (j = 1; j <= p; ++j)
            scanf("%d", t + j);
        a[i].val = Ordine(t);
        a[i].ind = i;
    }
}
inline bool cmp (const permut A, const permut B )
{
    if (A.val == B.val)
        return A.ind < B.ind;
    return A.val < B.val;
}
void Afisare()
{
    int i;
    freopen(outFile, "w", stdout);
    for (i = 1; i <= n; ++i)
        printf("%d\n", a[i].ind);
}
int main()
{
    Factoriale();
    Citire();
    sort(a + 1, a + n + 1, cmp);
    Afisare();
    return 0;
}
```

## Resurse

- [Pagina originală](https://codulluiandrei.ro/rezolvari/pbinfo/4712)
- [Sursa C++](https://codulluiandrei.ro/rezolvari/pbinfo/4712/cod.cpp)
- [Sursa pe GitHub](https://raw.githubusercontent.com/codulluiandrei/pbinfo/main/pbinfo-4712/main.cpp)
- [Cursuri de informatică pentru BAC](https://codulluiandrei.ro/academia/info-curs/pachet-cpp/)