Pagini recente » Cod sursa (job #1566763) | Cod sursa (job #1938127) | Cod sursa (job #1329375) | Cod sursa (job #164978) | Cod sursa (job #1275113)
#include <iostream>
#include <fstream>
#include <cstdlib>
#include <ctime>
using namespace std;
ifstream fin("schi.in");
ofstream fout("schi.out");
#define MAX 30010
struct T{
int s, key, priority;
T *left, *right;
void sum()
{
s = 1;
if(left)
s += left->s;
if(right)
s += right->s;
}
T(int k, int p, T* l, T* r)
{
key = k;
priority = p;
left = l;
right = r;
sum();
}
} *R, *nil;
void init()
{
srand(time(0));
R = nil = new T(0, 0, NULL, NULL);
R->s = 0;
nil->s = 0;
}
void rotL(T* &n)
{
T* x = n->left;
n->left = x->right;
x->right = n;
n->sum();
n = x;
n->sum();
}
void rotR(T* &n)
{
T* x = n->right;
n->right = x->left;
x->left = n;
n->sum();
n = x;
n->sum();
}
void balance(T* &n)
{
if(n->left->priority > n->priority)
rotL(n);
else if(n->right->priority < n->priority)
rotR(n);
}
void insert(T* &n, int key, int priority)
{
if(n == nil)
{
n = new T(key, priority, nil, nil);
return;
}
if(n->key > key)
{
insert(n->left, key, priority);
}
else
{
insert(n->right, key, priority);
}
n->sum();
balance(n);
}
void erase(T* &n, int key)
{
if(n == nil)
return;
if(n->key > key)
{
erase(n->left, key);
n->sum();
}
else if(n->key < key)
{
erase(n->right, key);
n->sum();
}
else
{
if(n->left == nil && n->right == nil)
{
delete n;
n = nil;
return;
}
if(n->left->priority > n->right->priority)
{
rotL(n);
erase(n->right, key);
}
else
{
rotR(n);
erase(n->left, key);
}
n->sum();
}
}
int kth_key(T* &n, int s)
{
if(n->s < s)
return -1;
if(n->left->s >= s)
return kth_key(n->left, s);
if(n->left->s + 1 == s)
return n->key;
return kth_key(n->right, s - (n->left->s + 1));
}
int a[MAX];
int rez[MAX];
unsigned const maxb = 8192;
char buf[maxb];
int ptr = maxb-1;
int getInt()
{
int rez = 0;
while(!(buf[ptr]>='0' && buf[ptr]<='9'))
{
if(++ptr>=maxb)
fin.read(buf, maxb), ptr=0;
}
while((buf[ptr]>='0' && buf[ptr]<='9'))
{
rez = rez * 10 + buf[ptr] - '0';
if(++ptr>=maxb)
fin.read(buf, maxb), ptr=0;
}
return rez;
}
int main()
{
int n, i;
init();
n = getInt();
for(i=1;i<=n;i++)
{
a[i] = getInt();
insert(R, i, rand()+1);
}
for(i = n ; i >= 1 ; i--)
{
int d = kth_key(R, a[i]);
rez[d] = i;
erase(R, d);
}
for(i = 1 ; i <= n ; i++)
{
fout << rez[i] << "\n";
}
}