Cod sursa(job #1148185)

Utilizator BlueStrutAndrei Prahoveanu BlueStrut Data 20 martie 2014 16:02:57
Problema Schi Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.92 kb
#include<cstdio>
#define zero(x) ((x^(x-1))&x)
using namespace std;
int i, n, a[30002], aib[30002], sol[300002], poz;
void scd(int poz){
    int i;
    for (i=poz;i<=n;i+=zero(i)) aib[i]--;
}
int sum(int x){
    int i, s=0;
    for (i=x;i>0;i-=zero(i))
        s+=aib[i];
    return s;
}
void cb(int st, int dr, int nr){
    int mij, x;
    for (mij=st+(dr-st)/2;st<=dr;mij=st+(dr-st)/2){
        x=sum(mij);
        if (x>nr) dr=mij-1;
        if (x<nr) st=mij+1;
        if (x==nr && mij<poz) poz=mij;
            else if (x==nr) dr=mij-1;
    }
}
int main(){
    freopen("schi.in","r",stdin);
    freopen("schi.out","w",stdout);
    scanf("%d",&n);
    for (i=1;i<=n;i++) {scanf("%d", &a[i]); aib[i]=zero(i);}
    for (i=n;i>=1;i--) {
        poz=n+1;
        cb(1, n, a[i]);
        sol[poz]=i;
        scd(poz);
    }
    for (i=1;i<=n;i++) printf("%d ", sol[i]);
    printf("\n"); return 0;
}