Cod sursa(job #1425363)

Utilizator killer301Ioan Andrei Nicolae killer301 Data 27 aprilie 2015 13:00:50
Problema Schi Scor 100
Compilator cpp Status done
Runda pregatire-lot-aib Marime 1.07 kb
#include <cstdio>

using namespace std;

const int nmax=30000;

int n;
int a[nmax+5];
int aib[nmax+5];
int sol[nmax+5];

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

void update(int pos, int val)
{
    for(int i=pos; i<=n; i+=lsb(i))
        aib[i] += val;
}

int binary(int k)
{
    int last;
    int ans = 0, sc = 0;
    for(int i=1<<15; i>0; i>>=1)
        if(ans + i<=n)
        {
            int pos = ans + i;
            int query_pos = sc + aib[pos];
            if(pos - query_pos < k)
            {
                ans += i;
                sc += aib[ans];
            }
            else if(pos - query_pos == k)
                last = ans + i;
        }
    return last;
}

int main()
{
    freopen("schi.in", "r", stdin);
    freopen("schi.out", "w", stdout);
    scanf("%d", &n);
    for(int i=1; i<=n; i++)
        scanf("%d", &a[i]);
    for(int i=n; i>0; i--)
    {
        int pos=binary(a[i]);
        sol[pos] = i;
        update(pos, 1);
    }
    for(int i=1; i<=n; i++)
        printf("%d\n", sol[i]);
    return 0;
}