Pagini recente » Cod sursa (job #2267831) | Cod sursa (job #2240541) | Cod sursa (job #2340131) | Cod sursa (job #179392) | Cod sursa (job #1477803)
/**
* Worg
*/
#include <ctime>
#include <cstdio>
#include <cstdlib>
using namespace std;
FILE *fin=freopen("schi.in","r",stdin);
FILE *fout=freopen("schi.out","w",stdout);
int v[30030], ans[30300];
int n;
struct treap {
int key, priority, total;
treap *left, *right;
treap(int key, int priority, int cnt, treap *left, treap *right) {
this->key = key, this->priority = priority, this->total = cnt;
this->left = left, this->right = right;
}
} *root, *empty;
void update(treap *&node) {
if(node == empty)
node->total = 0;
else
node->total = node->left->total + node->right->total + 1;
}
void rotLeft(treap *&node) {
treap *T = node->left;
node->left = T->right, T->right = node;
node = T;
update(node->right); update(node);
}
void rotRight(treap *&node) {
treap *T = node->right;
node->right = T->left, T->left = node;
node = T;
update(node->left); update(node);
}
void balance(treap *&node) {
if(node->priority < node->left->priority)
rotLeft(node);
else if(node->priority < node->right->priority)
rotRight(node);
}
void insert(treap *&node, int key) {
if(node == empty) {
node = new treap(key, rand() + 1, 1, empty, empty);
update(node);
return;
}
if(node->key > key)
insert(node->left, key);
else
insert(node->right, key);
update(node);
balance(node);
}
int under_key(treap *&node, int key) {
if(node == empty)
return 0;
if(node->key < key)
return node->left->total + 1 + under_key(node->right, key);
if(node->key == key)
return node->left->total + 1;
return under_key(node->left, key);
}
void write(treap *node) {
if(node == empty)
return;
write(node->left);
printf("%d ", node->key);
write(node->right);
}
void init() {
srand(unsigned(time(0)));
empty = root = new treap(0, 0, 0, NULL, NULL);
}
int main() {
init();
scanf("%d ", &n);
for(int i = 1; i <= n; ++i)
scanf("%d ", &v[i]);
int pos, N = n, last, add;
for(; n; --n) {
add = 0, pos = v[n];
do {
last = add;
add = under_key(root, pos);
pos += add - last;
}while(add != last);
ans[pos] = n;
insert(root, pos);
}
for(int i = 1; i <= N; ++i)
printf("%d\n", ans[i]);
return 0;
}