Cod sursa(job #856571)

Utilizator Stefex09Stefan Teodorescu Stefex09 Data 16 ianuarie 2013 18:51:41
Problema Schi Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.01 kb
//le varianta cu AIB

#include <iostream>
#include <fstream>

using namespace std;

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

int N;
int AIB[30010];
int Poz[30010], Sol[30010];

inline int LSB (int X)
{
    return (X & (-X));
}

inline int Update (int poz, int val)
{
    for ( ; poz <= N; poz += LSB (poz))
        AIB[poz] += val;
}

inline int Query (int poz)
{
    int ret = 0;

    for ( ; poz; poz -= LSB (poz))
        ret += AIB[poz];

    return ret;
}

inline int BS (int val)
{
    int i = N, step = 1 << 15;

    for ( ; step; step >>= 1)
        if (i - step >= 1 && Query (i - step) >= val)
            i -= step;

    return i;
}

int main()
{
    int i, now;

    in >> N;

    for (i = 1; i <= N; i ++){
        in >> Poz[i];
        Update (i, 1);
    }

    for (i = N; i; i --){
        now = BS (Poz[i]);
        Sol[now] = i;
        Update (now, -1);
    }

    for (i = 1; i <= N; i ++)
        out << Sol[i] << "\n";

    return 0;
}