Cod sursa(job #994718)

Utilizator ludacrivasilii teodorovici ludacri Data 6 septembrie 2013 09:43:36
Problema Schi Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.24 kb
#include <cstdio>
 
using namespace std;
 
#define arb_lung 65540
#define vec_lung 30005
#define usi unsigned short int
 
struct nod
{
   usi st,dr;
   usi sum;       
}arb[arb_lung];
 
usi v[vec_lung];
 
void uneste(nod &a,nod &b,nod &c)
{
   a.sum=b.sum+c.sum;
}
 
void build(usi st,usi dr,usi poz)
{
   arb[poz].st=st;
   arb[poz].dr=dr;
   if(st==dr)
   {
     arb[poz].sum=1;
     return;
   }
   usi mijl=(st+dr)>>1;
   build(st,mijl,poz<<1);
   build(mijl+1,dr,(poz<<1)+1);
   uneste(arb[poz],arb[poz<<1],arb[(poz<<1)+1]);
}
 
usi ith(usi i,usi poz)
{
   arb[poz].sum--; 
   if(arb[poz].st==arb[poz].dr)
     return arb[poz].st;
      
   if(i<=arb[poz<<1].sum)
     return ith(i,poz<<1);
   else
     return ith(i-arb[poz<<1].sum,(poz<<1)+1);     
}
 
int main()
{
    freopen("schi.in","r",stdin);
    freopen("schi.out","w",stdout);
     
    usi rasp[vec_lung];
    usi n,i,x;
    scanf("%hu",&n);
    for(i=1;i<=n;i++)
       scanf("%hu",&v[i]);
    build(1,n,1);
     
    for(i=n;i>=1;i--)
    {
       x=ith(v[i],1);
       rasp[x]=i;
       //update(x,1);  
    }
     
    for(i=1;i<=n;i++)
      printf("%hu\n",rasp[i]);
     
    //fin.close();
    //fout.close();
    return 0;
}