Cod sursa(job #874698)

Utilizator DaNutZ2UuUUBB Bora Dan DaNutZ2UuU Data 9 februarie 2013 10:33:57
Problema Schi Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.12 kb
#include <iostream>
#include <fstream>
#define NMAX 30100
using namespace std;

ifstream fin("schi.in");
ofstream fout("schi.out");

int N, sol[NMAX];
int v[NMAX];
int AIB[NMAX];

inline void update(int pos, int val)
{
    for (int i = pos; i <= N; i = (i | (i - 1)) + 1)
    {
        AIB[i] += val;
    }
}

inline int query(int pos)
{
    int res = 0;
    for (int i = pos; i >= 1; i = i & (i - 1))
    {
        res = res + AIB[i];
    }
    return res;
}

inline int bs(int position)
{
    int i = N, cnt = 1 << 20;
    for (; cnt > 0; cnt >>= 1)
    {
        if (i - cnt >= 1)
        {
            if (query(i - cnt) >= position) i -= cnt;
        }
    }
    return i;
}

int main()
{
    fin >> N;
    for (int i = 1; i <= N; ++i)
    {
        fin >> v[i];
    }
    for (int i = 1; i <= N; ++i)
    {
        update(i, 1);
    }

    for (int i = N; i >= 1; --i)
    {
        int abc = bs(v[i]);
        sol[abc] = i;
        update(abc, -1);
    }

    for (int i = 1; i <= N; ++i)
    {
        fout << sol[i] << '\n';
    }
    fout.close();
    return 0;
}