Cod sursa(job #1850859)

Utilizator Walrus21andrei Walrus21 Data 18 ianuarie 2017 23:19:59
Problema Schi Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.15 kb
#include <stdio.h>
#include <vector>
#include <algorithm>
#define N 30001

using namespace std;

int i, j, n, m, x, k, pz, v[N], A[4*N], s[N];

void up(int k, int l, int r, int p)
{
    if(l == r)
        A[k] ++;
    else
    {
        int m = (l + r) / 2;
        if(p <= m)
            up(2 * k, l, m, p);
        else
            up(2 * k + 1, m + 1, r, p);
        A[k] = A[2 * k] + A[2 * k + 1];
    }
}

int b()
{
    int m, ps, l = 1, r = n;
    while(l < r)
    {
        m = (l + r) / 2;
        ps = m - l + 1 - A[2 * k];
        if(x > ps)
        {
            k = 2 * k + 1;
            l = m + 1;
            x -= ps;
        }
        else
        {
            k *= 2;
            r = m;
        }
    }
    return l;
}

int main()
{
    freopen("schi.in", "r", stdin);
    freopen("schi.out", "w", stdout);
    scanf("%d", &n);
    for(i = 1; i <= n; i++)
        scanf("%d",&v[i]);
    for(i = n; i > 0; i--)
    {
        x = v[i];
        k = 1;
        pz = b();
        s[pz] = i;
        up(1, 1, n, pz);
    }
    for(i = 1; i <= n; i++)
        printf("%d\n", s[i]);
    return 0;
}