Cod sursa(job #3202902)

Utilizator Ruxandra009Ruxandra Vasilescu Ruxandra009 Data 12 februarie 2024 16:26:25
Problema Schi Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.96 kb
#include <fstream>

using namespace std;

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

const int nmax = 30005;
int n, aib[nmax], a[nmax], v[nmax];

int ub(int x){
    return (x&(-x));
}

void add(int x)
{
    for(int i = x; i <= n; i += ub(i))
        aib[i] --;
}

int sum(int x)
{
    int rez = 0;
    for(int i = x; i >= 1; i -= ub(i))
        rez += aib[i];

    return rez;
}


int main()
{
    f >> n;
    for(int i = 1; i <= n; i ++)
        f >> a[i];

    for(int i = 1; i <= n; i ++)
        aib[i] = ub(i);

    for(int i = n; i >= 1; i --)
    {
        int st = 1, dr = n, poz = -1;
        while(st <= dr && poz == -1)
        {
            int mij = (st + dr) / 2;
            if(sum(mij) > a[i])
                dr = mij - 1;
            else if(sum(mij) < a[i])
                st = mij + 1;
            else
                poz = mij;
        }

        add(poz);
        v[poz] = i;
    }

    for(int i = 1; i <= n; i ++)
        g << v[i] << '\n';
    return 0;
}