Cod sursa(job #3290840)

Utilizator robertcosacCosac Robert-Mihai robertcosac Data 1 aprilie 2025 12:07:14
Problema Schi Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.35 kb
#include <bits/stdc++.h>
using namespace std;
ifstream f("schi.in");
ofstream g("schi.out");
int v[100009], aint[400009], poz[400009], n;
void init (int nod, int st, int dr)
{
    if (st==dr) aint[nod]=1;
    else
    {
        int mij=(st+dr)/2;
        init (2*nod, st, mij);
        init (2*nod+1, mij+1, dr);
        aint[nod]=aint[2*nod]+aint[2*nod+1];
    }
}
void init ()
{
    init (1, 1, n);
}
int kth (int nod, int st, int dr, int k)
{
    if (st==dr) return st;
    int mij=(st+dr)/2;
    if (k<=aint[2*nod]) return kth (2*nod, st, mij, k);
    else return kth (2*nod+1, mij+1, dr, k-aint[2*nod]);
}
int kth (int k)
{
    return kth (1, 1, n, k);
}
void update (int nod, int st, int dr, int index, int value)
{
    if (st==dr) aint[nod]=value;
    else
    {
        int mij=(st+dr)/2;
        if (index<=mij) update (2*nod, st, mij, index, value);
        else update (2*nod+1, mij+1, dr, index, value);
        aint[nod]=aint[2*nod]+aint[2*nod+1];
    }
}
void update (int index, int value)
{
    update (1, 1, n, index, value);
}
int main ()
{
    f >> n;
    for (int i=1; i<=n; i++)
        f >> v[i];
    init ();
    for (int i=n; i>=1; i--)
    {
        int x=kth (v[i]);
        cout <<x << ' ';
        poz[x]=i;
        update (x, 0);
    }
    for (int i=1; i<=n; i++)
        g << poz[i] << '\n';
}