Cod sursa(job #2973243)

Utilizator rapidu36Victor Manz rapidu36 Data 31 ianuarie 2023 16:45:27
Problema Schi Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.19 kb
#include <fstream>

using namespace std;

const int L = 16;
const int N = 3e4;

ifstream in("schi.in");
ofstream out("schi.out");

int aint[1 << L], v[N + 1], clasament[N + 1];

void constructie(int p, int st, int dr)
{
    if (st == dr)
    {
        aint[p] = 1;
        return;
    }
    int m = (st + dr) / 2, fs = 2 * p, fd = 2 *  p + 1;
    constructie(fs, st, m);
    constructie(fd, m + 1, dr);
    aint[p] = aint[fs] + aint[fd];
}

int pozitie(int p, int st, int dr, int conc)
{
    if (st == dr)
    {
        aint[p]--;
        return st;
    }
    int m = (st + dr) / 2, fs = 2 * p, fd = 2 * p + 1, rez;
    if (aint[fs] >= conc)
    {
        rez = pozitie(fs, st, m, conc);
    }
    else
    {
        rez = pozitie(fd, m + 1, dr, conc - aint[fs]);
    }
    aint[p]--;
    return rez;
}

int main()
{
    int n;
    in >> n;
    constructie(1, 1, n);
    for (int i = 1; i <= n; i++)
    {
        in >> v[i];
    }
    for (int i = n; i >= 1; i--)
    {
        clasament[pozitie(1, 1, n, v[i])] = i;
    }
    for (int i = 1; i <= n; i++)
    {
        out << clasament[i] << "\n";
    }
    in.close();
    out.close();
    return 0;
}