Cod sursa(job #2981629)

Utilizator Paul281881818818181991919191881818Draghici Paul Paul281881818818181991919191881818 Data 18 februarie 2023 13:06:44
Problema Schi Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.57 kb
#include <fstream>
#include <iostream>
#include <vector>
std::ifstream fin("schi.in");
std::ofstream fout("schi.out");
class tree{
    public:
    int size;
    std::vector<int> list;
    tree(int n){
        size = n;
        list.resize(n+5);
    }
    void update(int pos, int diff);

    int query(int pos);

    int find(int value);

    void print();
};
int main(){
    int n;
    fin >> n;
    tree Tree(n);
    std::vector<int> positions(n+1), sol(n+1);
    for(int i = 1; i <= n; i++){
        fin >> positions[i];
    }
    //build tree
    for(int i = 1; i <= n; i++){
        Tree.update(i, 1);
    } 
    for(int i = n; i >= 1; i--){
        //find the pos[i] free pos
        int newPos = Tree.find(positions[i]);
        sol[newPos] = i;
        Tree.update(newPos, -1);
    }
    for(int i = 1; i <= n; i++){
        fout << sol[i] << "\n";
    }
}

void tree::update(int pos, int diff){
    while(pos <= size){
        list[pos] += diff;
        pos += (pos & -pos);
    }
}

int tree::query(int pos){
    int sum = 0;
    while(pos > 0){
        sum += list[pos];
        pos -= (pos & -pos);
    }
    return sum;
}

int tree::find(int value){
    int left = 1, right = size;
    while(left < right){
        int mid = left + (right - left)/2;
        int querymid = query(mid);
        if(value <= querymid){
            right = mid;
        }
        else {
            left = mid + 1;
        }
    }
    return right;
}

void tree::print(){
    for(auto it : list){
        std::cout << it << " ";
    }
}