Cod sursa(job #1260420)

Utilizator tatianazTatiana Zapirtan tatianaz Data 11 noiembrie 2014 11:47:30
Problema Schi Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.78 kb
#include <fstream>
using namespace std;

ifstream is("schi.in");
ofstream os("schi.out");

int n, a[30001], aib[30001], po[30001], sol;
int p;

void Update(int poz, int v)
{
    for ( int i = poz; i <= n; i += i & -i )
        aib[i] += v;

}

int BS(int v)
{
   int i = 0;
   for (int p = 1 << 16; p; p >>= 1 )
   {
        if ( i + p <= n && aib[i+p] < v )
        {
            v -= aib[i+p];
            i += p;
        }
   }
   return i + 1;
}

int main()
{
    is >> n;
    for ( int i = 1; i <= n; ++i )
    {
        is >> a[i];
        Update(i, 1);
    }

    for ( int i = n; i >= 1; --i )
    {
       sol = BS(a[i]);
       Update(sol, -1);
       po[sol] = i;
    }

    for ( int i = 1; i <= n; ++i )
        os << po[i] << '\n';

    is.close();
    os.close();
    return 0;
}