Cod sursa(job #1320746)

Utilizator serban_ioan97Ciofu Serban serban_ioan97 Data 18 ianuarie 2015 14:18:51
Problema Schi Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.02 kb
#include <cstdio>
#define lb(x) (x&(-x))
#define nmax 30030

using namespace std;

int aib[nmax];
int pos[nmax], final_pos[nmax];
int i, n, x;

void decrease(int x)
{
    for(int i=x; i<=n; i+=lb(i)) --aib[i];
}
int sum(int pos)
{
    int s=0;
    for(int i=pos; i>0; i-=lb(i)) s+=aib[i];
    return s;
}
int binary_search(int x)
{
    int left=1, right=n, mid, qq, minn=0x3f3f3f3f;

    while(left<=right)
    {
        mid=(left+right)/2;
        qq=sum(mid);
        if(qq==x && mid<minn) minn=mid;
        else if(qq>=x) right=mid-1;
            else left=mid+1;
    }
    return minn;
}
int main()
{
    freopen("schi.in", "rt", stdin);
    freopen("schi.out", "wt", stdout);

    scanf("%d", &n);

    for(i=1; i<=n; ++i)
    scanf("%d", &pos[i]);

    for(i=1; i<=n; ++i) aib[i]=lb(i);

    for(i=n; i>=1; --i)
    {
        x=binary_search(pos[i]);
        final_pos[x]=i;
        decrease(x);
    }

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

    return 0;
}