Cod sursa(job #3131165)

Utilizator MateitzaMatei Dinu Mateitza Data 19 mai 2023 13:16:05
Problema Schi Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.75 kb
#include <fstream>
#include <vector>
#include <algorithm>
#include <iostream>

using namespace std;

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

struct Node {
    int left, right;
    int value;
};

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

void buildTree(int node, int left, int right, const int position) {
    if (left == right) {
        tree[node].value = 1;
        return;
    }

    int mid = (left + right) / 2;
    if (position <= mid)
        buildTree(node * 2, left, mid, position);
    else
        buildTree(node * 2 + 1, mid + 1, right, position);

    tree[node].value = tree[node * 2].value + tree[node * 2 + 1].value;
}

int findPlace(int node, int left, int right, const int value) {
    if (left == right) {
        tree[node].value = 0;
        return left;
    }

    int mid = (left + right) / 2;
    int place;

    if (value <= tree[node * 2].value)
        place = findPlace(node * 2, left, mid, value);
    else
        place = findPlace(node * 2 + 1, mid + 1, right, value - tree[node * 2].value);

    tree[node].value = tree[node * 2].value + tree[node * 2 + 1].value;
    return place;
}

int main() {
    int numContestants;
    fin >> numContestants;

    vector<int> intermediateRank(numContestants + 1);
    vector<int> finalRank(numContestants + 1);

    for (int i = 1; i <= numContestants; ++i) {
        int rank;
        fin >> rank;
        intermediateRank[i] = rank;
        buildTree(1, 1, numContestants, i);
    }

    for (int j = numContestants; j > 0; --j) {
        finalRank[findPlace(1, 1, numContestants, intermediateRank[j])] = j;
    }

    for (int i = 1; i <= numContestants; ++i) {
        fout << finalRank[i] << "\n";
    }
    return 0;
}