Cod sursa(job #1350551)

Utilizator Pintilie_AndreiFII-Pintilie Andrei Pintilie_Andrei Data 20 februarie 2015 20:36:16
Problema Schi Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.3 kb
#include <iostream>
#include <fstream>
#define N 30005
using namespace std;
int a[2*N],s[N],b[N];
int n,start,stop,poz,val,k;
void Update(int nod,int st,int dr)
{
    if(st==dr)
    {
        a[nod]+=val;
        return ;
    }
    int mij=(st+dr)/2;
    if(poz<=mij) Update(2*nod,st,mij);
    else Update(2*nod+1,mij+1,dr);
    a[nod]=a[2*nod]+a[2*nod+1];
}
int Search(int nod, int x)
{
    //cout<<nod<<" ";
    if(a[nod]==x && nod>k)
    return (nod-k);
  //  if(a[nod]==x)  return Search(nod*2,x);
    if(a[nod]>=x) return Search(nod*2,x);
    if(a[nod]<x) {x-=a[nod]; return Search(nod+1,x); }
}
int main()
{
    ifstream fin("schi.in");
    ofstream fout("schi.out");
    fin>>n;
    int i,j;
    for(i=1; i<=n; i++)
    {
        fin>>b[i];
        poz=i;
        val=1;
        Update(1,1,n);
    }
    k=1;
    while(n>(1<<k)) k*=2;
    k=(1<<k)-n-1;
    //cout<<k<<"\n";
//        for(i=1; i<=2*n; i++)
//        cout<<a[i]<<" ";
//        cout<<"\n";
    for(i=n; i>=1; i--)
    {
        poz=Search(1,b[i]);
        val=-1;
        Update(1,1,n);
        s[poz]=i;
//        cout<<poz<<"\n";
//               for(j=1; j<=2*n; j++)
//        cout<<a[j]<<" ";
//        cout<<"\n";
    }
    for(i=1; i<=n; i++)
        fout<<s[i]<<"\n";

    return 0;
}