Cod sursa(job #1808237)

Utilizator BlackNestaAndrei Manaila BlackNesta Data 17 noiembrie 2016 15:47:13
Problema Schi Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.13 kb
#include <bits/stdc++.h>
#define Nmax 30005

using namespace std;

int v[Nmax], a[Nmax * 4 + 10], n, N, cl[Nmax];

inline void Read()
{
    ifstream f("schi.in");
    int i;
    f >> n;
    for(i = 1; i <= n; i++)
        f >> v[i];
    f.close();
}

inline void Update(int p)
{
    while(p > 0)
    {
        a[p]--;
        p /= 2;
    }
}

inline int Query(int x)
{
    int p = 1, f;
    while(p < N)
    {
        f = 2 * p;
        if(a[f] >= x)
            p = f;
        else
        {
            x -= a[f];
            p = f + 1;
        }
    }
    return p;
}

inline void Solve()
{
    int i, p;
    N = 1;
    while(N < n)
        N *= 2;
    for(i = N; i < N + n; i++)
        a[i] = 1;
    for(i = N - 1; i > 0; i--)
        a[i] = a[i * 2] + a[i * 2 + 1];
    for(i = n; i > 0; i--)
    {
        p = Query(v[i]);
        cl[p - N + 1] = i;
        Update(p);
    }
}

inline void Write()
{
    ofstream g("schi.out");
    for(int i = 1; i <= n; i++)
        g << cl[i] << "\n";
    g.close();
}

int main()
{
    Read();
    Solve();
    Write();
    return 0;
}