Cod sursa(job #1268491)

Utilizator TibiraducanuTiberiu Raducanu Tibiraducanu Data 20 noiembrie 2014 23:37:55
Problema Schi Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.93 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;
    scanf("%d",&n);
    for(i=1;i<=n;i++)
    {
        scanf("%d",&v[i]);
        update(i,1);
    }

    for(i=n;i>=1;i--)
    {
      in=1;
      sf=n;
      //printf("%d ",nr);
      while(in<=sf)
      {
          mij=(in+sf)>>1;
          if(query(mij)>=v[i])
          {
              sf=mij-1;
          }
          else in=mij+1;
      }

      update(in,-1);
      poz[in]=i;

    }

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

    return 0;
}