Pagini recente » Cod sursa (job #1769553) | Cod sursa (job #1987279) | Cod sursa (job #1870276) | Cod sursa (job #2160769) | Cod sursa (job #1477817)
/**
* 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];
int ans[30001];
int n, KEY;
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) {
if(node == empty) {
node = new treap(KEY, rand() + 1, empty, empty);
update(node);
return;
}
if(node->key > KEY)
insert(node->left);
else
insert(node->right);
update(node);
balance(node);
}
int under_key(treap *&node) {
if(node == empty)
return 0;
if(node->key < KEY)
return node->left->total + 1 + under_key(node->right);
if(node->key == KEY)
return node->left->total + 1;
return under_key(node->left);
}
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, KEY = mid, add = under_key(root);
if(v[n] + add <= mid)
sol = mid, right = mid - 1;
else
left = mid + 1;
}
ans[sol] = n;
KEY = sol, insert(root);
}
for(int i = 1; i <= N; ++i)
printf("%d\n", ans[i]);
return 0;
}