Cod sursa(job #1825621)

Utilizator d0rina2011Craciun Dorina d0rina2011 Data 9 decembrie 2016 15:09:44
Problema Schi Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.52 kb
#include <iostream>
#include <bits/stdc++.h>
#include <fstream>>

using namespace std;

ifstream fin("schi.in");
ofstream fout("schi.out");

int n, v[30001], aib[120001], sol[30001];

void build (int node, int left, int right)
{
    if(left == right)
        aib[node] = sol[left];
    else
    {
        int mid = (left + right) / 2;
        build(2 * node, left, mid);
        build(2 * node + 1, mid + 1, right);
        aib[node] = aib[2 * node] + aib[2 * node + 1];
    }
}
void update (int node, int left, int right, int x)
{
    if(right == left)
        aib[node] = x;
    else
    {
        int mid = (left + right)/2;
        if(mid >= x)
            update(2 * node, left, mid, x);
        else
            update(2 * node + 1, mid + 1, right, x);
        aib[node] = aib[2 * node] + aib[2 * node + 1];
    }
}
int query (int node, int left, int right, int x)
{
    if(left == right)
        return left;
    else
    {
        int mid = (left + right) / 2;
        if(x <= aib[2 * node])
            query(2 * node, left, mid, x);
        else
            query(2 * node + 1, mid + 1, right, x - aib[2 * node]);
    }
}

int main()
{
    int i;
    fin>>n;
    for(i = 1; i <= n; i++){
        fin>>v[i];
    }
    for(i = 1; i <= n; i++){
        update(1, 1, n, 1);
    }
    for(i = n; i >= 1; --i){
        int poz = query(1, 1, n, v[i]);
        sol[poz] = i;
        update(1, 1, n, 0);
    }
    for(i = 1; i <= n; ++i)
        fout<<sol[i]<<" ";
    return 0;
}