Cod sursa(job #1331784)

Utilizator Yasin_ibraimIbraim Yasin Yasin_ibraim Data 1 februarie 2015 10:55:55
Problema Schi Scor 95
Compilator cpp Status done
Runda tabaraichb Marime 1.06 kb
#include <stdio.h>

using namespace std;

int n, v[30005];
int arb[30005], sol[30005];

void update(int x)
{
    while (x<=n)
    {
        ++arb[x];
        x += x&(x-1)^x;
    }
}

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

    while (x)
    {
        sum += arb[x];
        x -= x&(x-1)^x;
    }
    return sum;
}

int bsearch(int x)
{
    int li=x+query(x), ls=n;
    int sol = ls;

    while (li<=ls)
    {
        int m=(li+ls)/2;

        if (m-query(m)>=x)
        {
            sol = m;
            ls = m-1;
        }
        else
        {
            li = m+1;
        }
    }
    return sol;
}

int main()
{
    FILE *fin,*fout;
    fin=fopen("schi.in", "r");
    fout=fopen("schi.out", "w");

    fscanf(fin,"%d", &n);

    for (int i=1; i<=n; ++i)
        fscanf(fin,"%d", &v[i]);

    int pos;

    for (int i=n; i; --i)
    {
        pos=bsearch(v[i]);
        sol[ bsearch(v[i]) ] = i;
        update(pos);
    }
    for (int i=1; i<=n; ++i)
        fprintf(fout,"%d \n", sol[i]);
    return 0;
}