Cod sursa(job #1152356)

Utilizator vyrtusRadu Criuleni vyrtus Data 24 martie 2014 17:50:42
Problema Schi Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.17 kb
#include <fstream>
#include <iostream>

#define nmax 30001
using namespace std;

ifstream f("schi.in");
ofstream g("schi.out");

int aib[nmax], poz[nmax] , sol[nmax];
int n;

inline void update(int pz , int val)
{
    while (pz <= n)
    {
        int p = 0;
         while (!(pz & (1 << p))) p++;
        aib[pz] += val;
        pz += (1 << p);
    }
}

inline int query(int pz)
{
    int sol = 0;
     while (pz)
     {
         int p = 0;
         while (!(pz & (1 << p) )) p++;
        sol += aib[pz];
        pz -= (1 << p);
     }
    return sol;
}

inline int search(int val)
{
    int s = 1; while (s<=n) s <<= 1;
    int i = 0;
     while (s)
     {
        if (i + s <= n && query(i+s) <= val)
            i += s;
        s >>=1;
     }
    return i;
}

int main()
{
    f >> n;
        for (int i=1;i<=n;i++)
            update(i,1);

      for (int i=1;i<=n;i++)
         f >> poz[i];

    for (int i=n;i>0;i--)
    {
        int x = poz[i];
         int t = search(x-1);
         sol[t+1] = i;
         update(t+1,-1);

    }

    for (int i=1;i<=n;i++)
    {
        g << sol[i] << '\n';
    }


    return 0;
}