Cod sursa(job #2086108)

Utilizator cyber_ghSoltan Gheorghe cyber_gh Data 11 decembrie 2017 14:40:50
Problema Schi Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.92 kb
#include <fstream>

#define ub(x) (x&(-x))

using namespace std;

ifstream f("schi.in");
ofstream g("schi.out");

int AIB[30005],S,i,j,sol[30005],n,m,a[30005],poz,pozi;

void dif (int x){
    for(j=x; j<=n; j+=ub(j))
        AIB[j]--;
}

int sum (int poz){
    int S=0;
    for(j=poz; j>0; j-=ub(j))
        S+=AIB[j];
    return S;
}


int cautare (int x)
{
    int st=1;
    int dr=n;
    int Min=30005;
    while(st<=dr)
    {
        m=(st+dr)/2;
        if(sum(m)==x&&m<Min)
        {
            Min=m;
            dr=m-1;
        }
        else if(sum(m)>x)
            dr=m-1;
        else st=m+1;
    }
    return Min;
}

int main(){
    f>>n;
    for(i=1; i<=n; i++){
        f>>a[i];
        AIB[i]=ub(i);
    }
    for(i=n; i>=1; i--){
        pozi=cautare(a[i]);
        sol[pozi]=i;
        dif(pozi);
    }
    for(i=1; i<=n; i++)
        g<<sol[i]<<'\n';
    return 0;
}