Cod sursa(job #828180)

Utilizator romircea2010FMI Trifan Mircea Mihai romircea2010 Data 3 decembrie 2012 12:22:16
Problema Schi Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.45 kb
#include <iostream>
#include <fstream>
#include <algorithm>

using namespace std;

int n, a[30010], aib[30010], sol[30010];
bool ocupat[30010];

inline void Read()
{
    ifstream f("schi.in");
    f>>n;
    int i;
    for(i=1; i<=n; i++)
        f>>a[i];
    f.close();
}

inline void Update(int poz, int x)
{
    while(poz<=n)
    {
        aib[poz]+=x;
        poz += (poz&-poz);
    }
}

inline int Query(int poz)
{
    int s = 0;
    while(poz)
    {
        s+=aib[poz];
        poz-=(poz&-poz);
    }
    return s;
}

inline int CautareBinara(int x)
{
    int st, dr, nr, mij;
    st = 1;
    dr = n;
    while(st<=dr)
    {
        mij = (st + dr)/2;
        nr = Query(mij);
        if (nr == x)
        {
            if (!ocupat[mij])
                return mij;
            else
                dr = mij - 1;
        }
        else
            if (nr < x)
                st = mij + 1;
            else
                dr = mij - 1;
    }
    return 0;
}

inline void Solve()
{
    int i, poz;
    for(i=1; i<=n; i++)
        Update(i, 1);
    for(i=n; i; i--)
    {
        poz = CautareBinara(a[i]);
        sol[poz] = i;
        ocupat[poz] = true;
        Update(poz, -1);
    }
}

inline void Write()
{
    ofstream g("schi.out");
    int i;
    for(i=1; i<=n; i++)
        g<<sol[i]<<"\n";
    g.close();
}

int main()
{
    Read();
    Solve();
    Write();
    return 0;
}