Cod sursa(job #1557079)

Utilizator DrumeaVDrumea Vasile DrumeaV Data 26 decembrie 2015 18:37:02
Problema Schi Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.96 kb
#include <stdio.h>
#include <algorithm>

using namespace std;

const int MN = 30005;

int N;
int t[MN],bit[MN],sol[MN],lsb[MN];

void update(int idx,int val)
{
    for (;idx <= N;bit[idx] += val,idx += idx & (-idx));
}

int query(int idx)
{
    int sum = 0;

    for (;idx;sum += bit[idx],idx -= idx & (-idx));

    return sum;
}

int bin_search(int x)
{
    int idx = 0;

    for (int it = 1 << 15;it;it >>= 1)
        if (idx + it <= N && query(idx + it) < x)
           idx += it;

    return idx + 1;
}

int main()
{
    freopen("schi.in","r",stdin);
    freopen("schi.out","w",stdout);

     scanf("%d",&N);

     for (int i = 1;i <= N;i++)
     {
         update(i,1);
         scanf("%d",&t[i]);
     }

     for (int i = N;i;i--)
     {
         int pos = bin_search(t[i]);

         update(pos,-1);
         sol[pos] = i;
     }

     for (int i = 1;i <= N;i++)
         printf("%d\n",sol[i]);

  return 0;
}