Cod sursa(job #1699895)

Utilizator Bodo171Bogdan Pop Bodo171 Data 8 mai 2016 19:31:17
Problema Schi Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.91 kb
#include <iostream>
#include<fstream>
using namespace std;
int i,v[30005],aib[30005],rasp[30005],n,aux,p,m,u,key;
inline int lbit(int x)
{
    return (x^(x-1)&x);
}
void update(int x,int val)
{
    for(x;x<=n;x+=lbit(x))
        aib[x]+=val;
}
int compute(int x)
{
    int sum=0;
    for(x;x>0;x-=lbit(x))
        sum+=aib[x];
    return sum;
}
int searchandconquer(int x)
{
    p=0;u=n+1;

    while(u-p>1)
    {
        m=(p+u)/2;
        key=compute(m);
        if(key<x) p=m;
        else u=m;
    }
    return u;

}
int main()
{
    ifstream f("schi.in");
    ofstream g("schi.out");
    f>>n;
    for(i=1;i<=n;i++)
    {
        f>>v[i];
        update(i,1);
    }
    aib[n+1]=(1<<30);
    for(i=n;i>=1;i--)
    {
        aux=searchandconquer(v[i]);
        rasp[aux]=i;
        update(aux,-1);
    }
    for(i=1;i<=n;i++)
        g<<rasp[i]<<'\n';
    return 0;
}