Pagini recente » Cod sursa (job #1177156) | Cod sursa (job #2847427) | Cod sursa (job #1707211) | Cod sursa (job #1290994) | Cod sursa (job #1477813)
/**
* Worg
*/
#include <ctime>
#include <cstdio>
#include <cstdlib>
using namespace std;
FILE *fin=freopen("schi.in","r",stdin);
FILE *fout=freopen("schi.out","w",stdout);
short int v[30001];
short int ans[30001];
int n;
struct treap {
int key, priority, total;
treap *left, *right;
treap(int key, int priority, treap *left, treap *right) {
this->key = key, this->priority = priority, this->total = 1;
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, 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, NULL, NULL);
empty->total = root->total = 0;
}
int main() {
init();
scanf("%d ", &n);
for(int i = 1; i <= n; ++i)
scanf("%d ", &v[i]);
int N = n, add, left, right, mid, sol;
for(; n; --n) {
left = v[n], right = N, sol = v[n];
while(left <= right) {
mid = (left + right) >> 1, add = under_key(root, mid);
if(v[n] + add <= mid)
sol = mid, right = mid - 1;
else
left = mid + 1;
}
ans[sol] = n;
insert(root, sol);
}
for(int i = 1; i <= N; ++i)
printf("%d\n", ans[i]);
return 0;
}