Cod sursa(job #1425536)

Utilizator badea_adi1999Badea Adrian Catalin badea_adi1999 Data 27 aprilie 2015 17:01:26
Problema Schi Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.85 kb
#include <fstream>
#define ub(i) i&(-i)
#define nmax 30010
using namespace std;
ifstream f("schi.in");
ofstream g("schi.out");
int v[nmax],aib[nmax];
int n,sol[nmax];


int aibsum(int poz)
{
    int sum=0;
    for (;poz>=1;poz-=ub(poz))
        sum+=aib[poz];
    return sum;
}
void aibadd(int poz,int val)
{
    for (;poz<=n;poz+=ub(poz))
        aib[poz]+=val;
}

int main()
{
    int i,j,x,st,dr;
    f>>n;
    for (i=1;i<=n;i++)
        f>>v[i];
    for (i=1;i<=n;i++)
        aibadd(i,1);
    for (i=n;i>=1;i--) {

        st=1,dr=n;
        while(st<=dr){
            int mij=(st+dr)>>1;
            if(aibsum(mij)>=v[i])
                dr=mij-1;
            else
                st=mij+1;
        }
        sol[st]=i;
        aibadd(st,-1);
    }
    for (i=1;i<=n;i++)
        g<<sol[i]<<'\n';
    return 0;
}