CCCPaste

Ordinea de rank a unui tablou

/*
    22 Martie 2025, Pahonie George-Alessio
    Ordinea de rank a unui tablou


    Se dau n elemente intr-un tablou.
    Sa se inlocuiasca fiecare element cu
    pozitia pe care s-ar afla daca tabloul
    ar fi sortat crescator. Daca avem elemente
    identice acestea vor primi aceiasi pozitie.

    Exemplu :   (indexare de la 1)
           Pozitia :  1 2 3 4 5
    tablou initial : {2,5,3,8,4}
    tabloul sortat : {2,3,4,5,8}
    de afisat      : {1,4,2,5,3}
    Explicatie : dupa ce vectorul este sortat -

    2 se afla pe pozitia 1
    5 se afla pe pozitia 4
    3 se afla pe pozitia 2
    8 se afla pe pozitia 5
    4 se afla pe pozitia 3

    Solutie in O(NlogN) cu functia sort.

*/

#include 
#include 
using namespace std;
int v[10005],p[10005], r[10005];
bool cmp(int a, int b)
{
    return v[a] < v[b];
}
int main()
{
    int n;
    cin >> n;
    for(int i = 1;i<=n;i++)
    {
        cin >> v[i];
        p[i] = i;
    }
    sort(p+1,p+n+1,cmp);
    /// Acum v[p[i]] este tabloul v sortat crescator.
    // Adica p[i] = pozitia elementului i din v sortat crescator (exact ce avem nevoie)
    /*
    for(int i = 1;i<=n;i++)
        cout << v[p[i]] << ' ';
    cout << '\n';
    */

    int cnt = 1;
    r[p[1]] = cnt;
    for(int i = 2;i<=n;i++)
    {
        // Daca in v sortat elementele nu sunt identice
        // atunci avem un element nou.
        if(v[p[i]] != v[p[i-1]])
            cnt++;
        r[p[i]] = cnt;
    }
    for(int i = 1;i<=n;i++)
        cout << r[i] << ' ';
    return 0;
}