Cod sursa(job #1747490)

Utilizator denniscrevusDennis Curti denniscrevus Data 24 august 2016 23:23:35
Problema Schi Scor 70
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.85 kb
#include <fstream>
#define NMAX 30010

using namespace std;

int v[NMAX],i,n,x,j;
bool b[NMAX];
int arb[3*NMAX],ans[NMAX];

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

void initializare()
{
    for(i=1;i<=n;i++)
        b[i]=1;
}

void update(const int &st, const int &dr, const int &poz, const int &nod)
{
    if(st==dr)
    {
        arb[nod]=b[poz];
        return;
    }
    int mij=((st+dr)>>1);
    int sfiu=(nod<<1);
    int dfiu=((nod<<1)+1);
    if(poz<=mij)
        update(st,mij,poz,sfiu);
    if(poz>mij)
        update(mij+1,dr,poz,dfiu);
    arb[nod]=arb[sfiu]+arb[dfiu];
}

int querry(const int &st, const int &dr, const int &st1, const int &dr1, const int &nod)
{
    if(st1==st && dr==dr1)
        return arb[nod];

    int mij=((st+dr)>>1);
    int sfiu=(nod<<1);
    int dfiu=((nod<<1)+1);

    if(dr1<=mij)
        return querry(st,mij,st1,dr1,sfiu);
    if(st1>mij)
        return querry(mij+1,dr,st1,dr1,dfiu);

    return (querry(st,mij,st1,mij,sfiu) + querry(mij+1,dr, mij+1,dr1,dfiu));
}

int cautbin(int sum)
{
    int start=0;
    int step=1;

    for(;step<n;step<<=1);
    for(;step;step>>=1)
    {
        int index=start+step;
        if(index>n)
            continue;
        if(querry(1,n,1,index,1)<sum)
        {
            //g<<querry(1,n,1,index,1)<<" "<<index<<"\n";
            start=index;
        }
    }
    return start+1;
}

int main()
{
    f>>n;

    initializare();

    for(i=1;i<=n;i++)
    {
        f>>v[i];
        update(1,n,i,1);
    }

    for(i=n;i>=1;i--)
    {
        x=cautbin(v[i]);

        //g<<x<<"\n";

        b[x]=0;

        ans[x]=i;

        update(1,n,x,1);

        //g<<"\n";
        /*for(j=1;j<=3*n;j++)
            g<<arb[j]<<" ";
        */
    }
    //g<<"\n";
    for(i=1;i<=n;i++)
        g<<ans[i]<<"\n";
}