Cod sursa(job #1846903)

Utilizator horatiucheval2Horatiu Andrei Cheval horatiucheval2 Data 14 ianuarie 2017 09:41:20
Problema Schi Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.27 kb
#include <iostream>
#include <fstream>
using namespace std;

const int MAX = 30000;
int tree[4 * MAX];

void update(int left, int right, int node, int val, int pos){
    if(left == right){
        tree[node] = val;
    }else{
        int mid = (left + right) / 2;
        if(pos <= mid){
            update(left, mid, 2 * node, val, pos);
        }else{
            update(mid + 1, right, 2 * node + 1, val, pos);
        }
        tree[node] = tree[2 * node] + tree[2 * node + 1];
    }
}

int query(int left, int right, int node, int n){
    if(left == right){
        return left;
    }
    int mid = (left + right) / 2;
    if(tree[2 * node] >= n){
        return query(left, mid, 2 * node, n);
    }else{
        return query(mid + 1, right, 2 * node + 1, n - tree[2 * node]);
    }
}

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

    int n, v[MAX], ord[MAX];
    fin >> n;
    for(int i = 0; i < n; i++){
        fin >> v[i];
    }

    for(int i = 1; i <= n; i++){
        update(1, n, 1, 1, i);
    }

    for(int i = n - 1; i >= 0; i--){
        int x = query(1, n, 1, v[i]);
        ord[x] = i;
        update(1, n, 1, 0, x);
    }

    for(int i = 1; i <= n; i++){
        fout << ord[i] + 1 << " ";
    }

    fin.close();
    fout.close();
    return 0;
}