Cod sursa(job #1999705)

Utilizator sfechisalin@yahoo.comSfechis Alin [email protected] Data 11 iulie 2017 21:43:56
Problema Schi Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.99 kb
#include <bits/stdc++.h>

#define LSB(x) ( (x) & (-x) )
using namespace std;
ifstream fin("schi.in");
ofstream fout("schi.out");

vector<int> rang, bit, answer;
int n;

void update(int poz, int val)
{
    for (; poz <= n; poz += LSB(poz))
        bit[poz] += val;
}

int query(int poz)
{
    int answ = 0;
    for (; poz; poz -= LSB(poz))
        answ += bit[poz];
    return answ;
}

int main()
{
    fin >> n;
    rang.resize(n + 1);
    bit.resize(n + 1);
    answer.resize(n + 1);

    for (int i = 1; i <= n; ++i)
        fin >> rang[i], update(i, 1);

    int p = 1;
    for (; p < n; p <<= 1);


    for (int i = n ; i >= 1; i--)
    {
        int k, step;
        for (k = 0, step = p; step; step >>= 1)
            if (k + step <= n && query(k + step) < rang[i])
                k += step;

        answer[k + 1] = i;
        update( k + 1, -1 );
    }

    for (int i = 1; i < answer.size(); ++i)
        fout << answer[i] << "\n";

    return 0;
}