Cod sursa(job #3324075)

Utilizator Andrei1209Andrei Mircea Andrei1209 Data 20 noiembrie 2025 21:48:59
Problema Schi Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.81 kb
#include <fstream>
#include <vector>

using namespace std;
ifstream fin("schi.in");
ofstream fout("schi.out");
const int nmax = 30000 + 5;
int taken[nmax], aint[4 * nmax ], v[nmax], sol[nmax];

void build(int st, int dr, int nod )
{
    if ( st == dr )
    {
        if ( taken[st] == 0 )///e liber
            aint[nod] = 1;
        return ;
    }
    int mij = (st + dr) / 2;
    build(st, mij, 2 * nod);
    build( mij + 1, dr, 2 * nod + 1 );
    aint[nod] = aint[ nod * 2] + aint[nod * 2 + 1];
    //fout << "st = " << st << " dr = " << dr << " nr de 0 din interval = " << aint[nod] << endl;
}
void update( int st, int dr, int nod, int poz )
{
    if ( st == dr )
    {
        if ( taken[st] == 0 )///e liber
            aint[nod] = 1;
        else
            aint[nod] = 0;
        return ;
    }
    int mij = (st + dr) / 2;
    if ( poz <= mij )
        update(st, mij, 2 * nod, poz );
    else
        update(mij + 1, dr, 2 * nod + 1, poz );
    aint[nod] = aint[ nod * 2] + aint[nod * 2 + 1];


}
int querry( int st, int dr, int nod, int x )
{
    //fout << " st = "<< st << " dr = " << dr << " aint = " << aint[nod * 2] << " , " << aint[nod * 2 + 1] << endl;
    if ( st == dr)
        return st;

    int mij = (st + dr) / 2;
    if ( aint[nod * 2] >= x )
        return querry(st, mij, nod * 2, x);
    else
        return querry(mij + 1, dr, nod * 2 + 1, x - aint[nod * 2]);

}
int main()
{
    int n, i;
    fin >> n;
    for ( i = 1; i <= n; ++i )
        fin >> v[i];
    build(1, n, 1);
 //   fout << "-------------------\n";
    for ( i = n; i >= 1; --i )
    {
        int poz = querry(1, n, 1, v[i]);
        sol[poz] = i;
        taken[poz] = 1;
        update(1, n, 1, poz);
    }
    for ( i = 1; i <= n; ++i )
        fout << sol[i] << '\n';
    return 0;
}