Cod sursa(job #1268467)

Utilizator TibiraducanuTiberiu Raducanu Tibiraducanu Data 20 noiembrie 2014 23:15:10
Problema Schi Scor 90
Compilator cpp Status done
Runda Arhiva de probleme Marime 1 kb
#include <cstdio>

using namespace std;
int n,aib[30005],v[30005],poz[30005];
int lsb(int x)
{
    return (x&(-x));
}
void update(int poz,int val)
{
    for(int i=poz;i<=n;i+=lsb(i))
        aib[i]+=val;
}

int query(int poz)
{
    int s=0;
    while(poz)
    {
        s+=aib[poz];
        poz-=lsb(poz);
    }
    return s;
}

int main()
{
    freopen("schi.in","r",stdin);
    freopen("schi.out","w",stdout);
    int i,in,sf,mij,last;
    scanf("%d",&n);
    for(i=1;i<=n;i++)
        scanf("%d",&v[i]);

    poz[v[n]]=n;
    update(v[n],1);

    for(i=n-1;i>=1;i--)
    {
      last=-1;
      in=1;
      sf=n;
      //printf("%d ",nr);

        while(in<=sf)
        {
          mij=(in+sf)/2;
          if(query(mij)+v[i]<=mij)
          {
              last=mij;
              sf=mij-1;
          }
          else in=mij+1;
        }

        update(last,1);
        poz[last]=i;

    }

    for(int j=1;j<=n;j++) printf("%d\n",poz[j]);

    return 0;
}