Cod sursa(job #1710542)

Utilizator leopop29Pop Leonard leopop29 Data 29 mai 2016 11:34:03
Problema Schi Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.97 kb
#include <iostream>
#include <fstream>
#define NM 30005

using namespace std;

int ai[NM], in[NM], r[NM];
int n;

inline int lsb(int x)
{
    return ((x&(x-1))^x);
}

void init()
{
    for(int i = 1; i <= NM; ++i)
        for(int p = i; p < NM; p += lsb(p))
            ++ai[p];
}

void upd(int x)
{
    for(int p = x; p < NM; p += lsb(p))
        --ai[p];
}

int qr(int x)
{
    int sm = 0;
    for(; x; x -= lsb(x))
        sm += ai[x];
    return sm;
}

int sr(int x)
{
    int st, p = 0;
    for(st = 1; st <= n; st <<= 1);
    st >>= 1;
    for(; st; st >>= 1)
        if(qr(p+st) < x)
            p += st;
    ++p;

    upd(p);
    return p;
}

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

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

    for(int i = n; i; i--)
    {
        r[sr(in[i])] = i;
    }

    for(int i = 1; i <= n; ++i)
        cout << r[i] << '\n';
}