Cod sursa(job #3132735)

Utilizator FastmateiMatei Mocanu Fastmatei Data 23 mai 2023 18:53:04
Problema Schi Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.29 kb
#include <iostream>
#include <fstream>

using namespace std;

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

int aint[120005];
int a[30005];
int n;
int sol[30005];

void Build(int nod, int st, int dr)
{
    if (st == dr)
    {
        aint[nod] = 1;
        return;
    }
    int mij = (st + dr) / 2;
    Build(2 * nod, st, mij);
    Build(2 * nod + 1, mij + 1, dr);
    aint[nod] = aint[2 * nod] + aint[2 * nod + 1];
}
void Update(int nod, int st, int dr, int poz)
{
    if (st == dr)
    {
        aint[nod] = 0;
        return;
    }
    int mij = (st + dr) / 2;
    if (poz <= mij) Update(2 * nod, st, mij, poz);
    else Update(2 * nod + 1, mij + 1, dr, poz);
    aint[nod] = aint[2 * nod] + aint[2 * nod + 1];
}


int Query(int nod, int st, int dr, int x)
{
    if (st == dr) return st;
    int mij = (st + dr) / 2;
    if (x <= aint[2 * nod]) return Query(2 * nod, st, mij, x);
    else return Query(2 * nod + 1, mij + 1, dr, x - aint[2 * nod]);
}

int main()
{
    fin >> n;
    for (int i = 1; i <= n; i++)
        fin >> a[i];
    Build(1, 1, n);
    for (int i = n; i >= 1; i--)
    {
        int x = Query(1, 1, n, a[i]);
        Update(1, 1, n, x);
        sol[x] = i;
    }
    for (int i = 1; i <= n; i++)
        fout << sol[i] << "\n";
}