Cod sursa(job #1600557)

Utilizator Cristian1997Vintur Cristian Cristian1997 Data 15 februarie 2016 10:02:57
Problema Schi Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.26 kb
#include <fstream>
#include <vector>
using namespace std;
#define Nmax 30001

struct aib
{
    int n;
    vector< int > v;
    
    void resize(int nr)
    {
        n = nr;
        v.assign(n + 1, 0);
    }
    void set_1(int p)
    {
        for(; p <= n; p += p & -p) ++v[p];
    }
    void set_0(int p)
    {
        for(; p <= n; p += p & -p) --v[p];
    }
    int kth_element(int k)
    {
        int step, p;
        
        for(step = 1; step <= n; step <<= 1) ;
        for(p = 0; step; step >>= 1)
            if(p + step <= n && v[p + step] < k)
                k -= v[p + step],
                p += step;
        
        return p + 1;
    }
};

vector< int > v, order;
aib pos;

int main()
{
    int i, n, p;
    ifstream fin("schi.in");
    ofstream fout("schi.out");
    
    fin >> n;
    v.resize(n + 1);
    order.resize(n + 1);
    pos.resize(n);
    
    for(i = 1; i <= n; ++i) fin >> v[i];
    
    for(i = 1; i <= n; ++i) pos.set_1(i);
    
    for(i = n; i >= 1; --i)
    {
        p = pos.kth_element(v[i]);
        pos.set_0(p);
        
        order[p] = i;
    }
    
    for(i = 1; i <= n; ++i)
        fout << order[i] << '\n';
    
    fin.close();
    fout.close();
    
    return 0;
}