Cod sursa(job #613094)

Utilizator vladtarniceruVlad Tarniceru vladtarniceru Data 15 septembrie 2011 20:19:54
Problema Schi Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.8 kb
#include <fstream>
using namespace std;

int n, v[30100], a[30100], sol[30100];

void adauga(int x)
{
    for (int i = x; i <= n; i += i & -i)
        ++a[i];
}
int suma(int x)
{
    int ret = 0;
    for (int i = x - 1; i > 0; i -= i & -i)
        ret += a[i];
    return ret;
}
int bs(int x)
{
    int i, cnt;
    for (i = 1, cnt = 1 << 17; cnt > 0; cnt >>= 1)
        if (i + cnt <= n)
            if (suma(i + cnt) >= (i + cnt) - x) i += cnt;
    return i;
}

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

    f >> n;
    for (int i = 1; i <= n; ++i)
        f >> v[i];

    for (int i = n; i >= 1; --i)
    {
        int val = bs(v[i]);
        sol[val] = i;
        adauga(val);
    }
    for (int i = 1; i <= n; ++i)
        g << sol[i] << '\n';
}