Cod sursa(job #2908562)

Utilizator AswVwsACamburu Luca AswVwsA Data 4 iunie 2022 13:09:19
Problema Schi Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 3.08 kb
//these are confusing times
//treapunealta secreta, ca-s prea prost sa invat cum se face normal
#include <fstream>
#include <random>
#include <ctime>
#define ll long long
using namespace std;

mt19937 generator(time(NULL));

class Node
{
public:
    int value;
    int priority;
    int size;
    Node* left = nullptr;
    Node* right = nullptr;

    Node(int value = 0)
    {
        this->value = value;
        this->priority = generator();
        this->size = 1;
    }

    void update()
    {
        this->size = 1;
        if (this->left != nullptr)
            this->size += this->left->size;
        if (this->right != nullptr)
            this->size += this->right->size;
    }
};

pair<Node*, Node*> split(Node* node, int value)
{
    if (node == nullptr)
    {
        return {nullptr, nullptr};
    }
    else if (node->value <= value)
    {
        pair<Node*, Node*> aux = split(node->right, value);
        node->right = aux.first;
        node->update();
        return {node, aux.second};
    }
    else
    {
        pair<Node*, Node*> aux = split(node->left, value);
        node->left = aux.second;
        node->update();
        return {aux.first, node};
    }
}

Node* merge(Node* left, Node* right)
{
    if (left == nullptr)
    {
        return right;
    }
    else if (right == nullptr)
    {
        return left;
    }
    else
    {
        if (left->priority > right->priority)
        {
            left->right = merge(left->right, right);
            left->update();
            return left;
        }
        else
        {
            right->left = merge(left, right->left);
            right->update();
            return right;
        }
    }
}

Node* insert(Node* node, int value)
{
    pair <Node*, Node*> aux = split(node, value);
    Node* curr = new Node(value);
    aux.first = merge(aux.first, curr);
    return merge(aux.first, aux.second);
}

Node* erase(Node* node, int value)
{
    pair<Node*, Node*> first_split = split(node, value);
    pair<Node*, Node*> left_split = split(first_split.first, value - 1);
    delete left_split.second;
    return merge(left_split.first, first_split.second);
}

int nth_element(Node* node, const int n)
{
    if (node == nullptr)
    {
        //cerr << "No such element" << endl;
        return 0;
    }
    int left_size = (node->left ? node->left->size : 0);
    if (left_size >= n)
        return nth_element(node->left, n);
    else if (left_size + 1 < n)
        return nth_element(node->right, n - left_size - 1);
    else
        return node->value;
}

int v[30003], ans[30003];
int main()
{
    ifstream cin("schi.in");
    ofstream cout("schi.out");
    Node* root = nullptr;
    int n, i;
    cin >> n;
    for (i = 1; i <= n; i++)
    {
        cin >> v[i];
        root = insert(root, i);
    }
    for (i = n; i >= 1; i--)
    {
        int val = nth_element(root, v[i]);
        ans[val] = i;
        root = erase(root, val);
    }
    for (i = 1; i <= n; i++)
        cout << ans[i] << "\n";
    return 0;
}