Cod sursa(job #2754576)

Utilizator Maria23Dutu Maria Maria23 Data 26 mai 2021 00:41:18
Problema Schi Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.37 kb
#include <fstream>
#include <vector>
#include <algorithm>

using namespace std;

ifstream cin ("schi.in");
ofstream cout ("schi.out");

const int Nmax = 30000;
vector<int> tree(4*Nmax);

void form_tree(int node, int l, int r, const int poz){
    if(l == r){
        tree[node] = 1;
        return;
    }

    int mid = (l + r) / 2;
    if(poz <= mid)
        form_tree(node * 2, l, mid, poz);
    else
        form_tree(node * 2 + 1, mid + 1, r, poz);
    tree[node] = tree[node * 2] + tree[node * 2 + 1];
}


int find_place(int node, int l, int r, const int val){
    if(l == r){
        tree[node] = 0;
        return l;
    }
    int mid = (l + r) / 2, place;

    if(val <= tree[node * 2])
        place = find_place(node * 2, l, mid, val);
    else
        place = find_place(node * 2 + 1, mid + 1, r, val - tree[node*2]);
    tree[node] = tree[node * 2] + tree[node * 2 + 1];
    return place;
}

int main() {
    int nrC;
    cin >> nrC;
    vector<int> clasament_int(nrC + 1);
    vector<int> clasament_fin(nrC + 1);
    for (int i = 1; i <= nrC; ++ i) {
        int x;
        cin >> x;
        clasament_int[i] = x;
        clasament_int[i] = x;
        form_tree(1, 1, nrC, i);
    }

    for(int j = nrC; j > 0; j--){
        clasament_fin[find_place(1, 1, nrC,  clasament_int[j])] = j;
        }

    for(int i = 1; i <= nrC; i++){
        cout<<clasament_fin[i]<<"\n";
    }
    return 0;
}