Cod sursa(job #1747505)

Utilizator denniscrevusDennis Curti denniscrevus Data 25 august 2016 00:22:40
Problema Schi Scor 70
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.29 kb
#include <cstdio>
#define NMAX 30010
#define DIM 10000

using namespace std;

char buff[DIM];
int v[NMAX],i,n,x,j,start,step,poz=0;
bool b[NMAX];
int arb[3*NMAX],ans[NMAX];

void citeste(int &numar)
{
     numar = 0;
     while (buff[poz] < '0' || buff[poz] > '9')
     {
          if (++poz == DIM)
               fread(buff,1,DIM,stdin),poz=0;
     }
     while ('0'<=buff[poz] && buff[poz]<='9')
     {
          numar = numar*10 + buff[poz] - '0';
          if (++poz == DIM)
               fread(buff,1,DIM,stdin),poz=0;
     }
}

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

void build(const int &st, const int &dr, const int &nod)
{
    if(st==dr)
    {
        arb[nod]=1;
        return;
    }
    int mij=((st+dr)>>1);
    build(st,mij,2*nod);
    build(mij+1,dr,2*nod+1);
    arb[nod]=arb[2*nod]+arb[2*nod+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);
    if(poz<=mij)
        update(st,mij,poz,2*nod);
    else
        update(mij+1,dr,poz,2*nod+1);
    arb[nod]=arb[2*nod]+arb[2*nod+1];
}

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);

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

    return (querry(st,mij,st1,mij,(nod<<1)) + querry(mij+1,dr, mij+1,dr1,((nod<<1)|1)));
}

int cautbin(int sum)
{
    start=0;
    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)
            start=index;

    }
    return start+1;
}

int main()
{
    freopen("schi.in","r",stdin);
    freopen("schi.out", "w", stdout);

    citeste(n);

    initializare();

    for(i=1;i<=n;i++)
    {
        citeste(v[i]);
    }

    build(1,n,1);

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

        b[x]=0;

        ans[x]=i;

        update(1,n,x,1);

    }
    //g<<"\n";
    for(i=1;i<=n;i++)
        printf("%d\n", ans[i]);
}