Cod sursa(job #1275113)

Utilizator sebinechitasebi nechita sebinechita Data 24 noiembrie 2014 19:44:28
Problema Schi Scor 45
Compilator cpp Status done
Runda Arhiva de probleme Marime 3.01 kb
#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";
    }

}