Cod sursa(job #169692)

Utilizator cretuMusina Rares cretu Data 1 aprilie 2008 21:12:55
Problema Schi Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.42 kb
#include <fstream>
#define m ((st+dr)>>1)
#define ns (nod<<1)
#define nd (ns+1)
#define MAX (1<<15)
#define INF 99999
#define mini(a, b) ((a) < (b) ? (a) : (b))

using namespace std;

int s[MAX], val[MAX], p[MAX<<1];
int n, poz, concurent, a, b;

void Build(int nod, int st, int dr)
{
     if (st == dr) 
     {
         p[nod] = 1;
         return;       
     }     
     
     Build(ns, st,  m);
     Build(nd, m+1, dr);
     
     p[nod] = p[ns] + p[nd];
}

int Query(int nod, int st, int dr, int nr)
{
    if (st == dr) { return st; }
    
    if (nr <= p[ns]) return Query(ns, st,  m,  nr);
    else             return Query(nd, m+1, dr, nr-p[ns]);
}

void Update(int nod, int st, int dr)
{
     if (st == dr)
     {
         p[nod]--;
         return;       
     }    
     
     if (poz <= m) Update(ns, st,  m);
     else          Update(nd, m+1, dr);
     
     p[nod] = p[ns] + p[nd];
}

int main()
{
    int i, j, ok;
    ifstream fin("schi.in");
    fin >> n;
    for (i = 1; i <= n; i++)   
    { 
        fin >> val[i];
        s[i] = 0;
    }
    fin.close();
    
    Build(1, 1, n);
    
    for (i = n; i >= 1; i--)
    {
        poz = Query(1, 1, n, val[i]);
        s[poz] = i;
        Update(1, 1, n);        
    }
    
    ofstream fout("schi.out");
    for (i = 1; i <= n; i++)
        fout << s[i] << "\n";
    fout.close();
    
    return 0;
}