Pagini recente » Cod sursa (job #1402381) | Cod sursa (job #1904233) | Cod sursa (job #2542007) | Cod sursa (job #596086) | Cod sursa (job #2908562)
//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;
}