Cod sursa(job #962058)

Utilizator Andrei1998Andrei Constantinescu Andrei1998 Data 13 iunie 2013 18:42:54
Problema Schi Scor 70
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.5 kb
#include <fstream>

using namespace std;

#define arb_lung 65540
#define vec_lung 30005

struct nod
{
   int st,dr;
   int sum;       
}arb[arb_lung];

int v[vec_lung];

void uneste(nod &a,nod &b,nod &c)
{
   a.sum=b.sum+c.sum;
}

void build(int st,int dr,int poz)
{
   arb[poz].st=st;
   arb[poz].dr=dr;
   if(st==dr)
   {
     arb[poz].sum=1;
     return;
   }
   int 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]);
}

int ith(int i,int poz)
{
   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);     
}

void update(int unde,int poz)
{
   if(arb[poz].st==arb[poz].dr && arb[poz].st==unde)
   {             
      arb[poz].sum=0;
      return;   
   }
   int mijl=(arb[poz].st+arb[poz].dr)>>1;
   if(unde<=mijl)
     update(unde,poz<<1);
   else
     update(unde,(poz<<1)+1);
   uneste(arb[poz],arb[poz<<1],arb[(poz<<1)+1]);
}

int main()
{
    ifstream fin("schi.in");
    ofstream fout("schi.out");
    
    int rasp[vec_lung];
    int n,i,x;
    fin>>n;
    for(i=1;i<=n;i++)
      fin>>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++)
      fout<<rasp[i]<<'\n';
    
    fin.close();
    fout.close();
    //system("PAUSE");
    return 0;
}