Cod sursa(job #1773962)

Utilizator StarGold2Emanuel Nrx StarGold2 Data 8 octombrie 2016 13:37:40
Problema Order Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 3.02 kb
#include <bits/stdc++.h>
using namespace std;

ifstream in ( "order.in"  );
ofstream out( "order.out" );

struct T {
    int key, pr, sz;
    T *l, *r;

    T() {
        this -> pr = INT_MIN; this -> sz = 0;
        this -> l = NULL; this -> r = NULL;
    }

    T( int key, int pr, T *l, T *r ) {
        this -> key = key; this -> pr = pr; this -> sz = 1;
        this -> l = l; this -> r = r;
    }
} *r, *nil;

T* update( T *t ) {
    if( t == nil )
        return t;

    t -> sz = 1 + t -> l -> sz + t -> r -> sz;
    return t;
}

pair<T*, T*> split( T *t, int p ) {
    pair<T*, T*> aux; t = update( t );

    if( t == nil )
        return make_pair( t, t );

    if( t -> l -> sz + 1 > p ) {
        aux = split( t -> l, p );
        t -> l = aux.second; aux.second = t;
    } else {
        aux = split( t -> r, p - (t -> l -> sz + 1) );
        t -> r = aux.first; aux.first = t;
    }

    update( t );
    return aux;
};

T* join( T *lt, T *rt ) {
    lt = update( lt ); rt = update( rt );

    if( lt == nil ) return rt;
    if( rt == nil ) return lt;

    if( lt -> pr > rt -> pr ) {
        lt -> r = join( lt -> r, rt );
        lt = update( lt ); return lt;
    } else {
        rt -> l = join( lt, rt -> l );
        rt = update( rt ); return rt;
    }
}

T* insert( T *t, int p, int key, int pr ) {
    t = update( t ); pair<T*, T*> aux;

    if( pr > t -> pr ) {
        aux = split( t, p );
        t = new T( key, pr, aux.first, aux.second );
    } else {
        if( t -> l -> sz + 1 >= p )
            t -> l = insert( t -> l, p, key, pr );
        else
            t -> r = insert( t -> r, p - (t -> l -> sz + 1), key, pr );
    }

    t = update( t );
    return t;
}

T* erase( T *t, int p ) {
    t = update( t ); T *aux;

    if( t -> l -> sz + 1 == p ) {
        aux = join( t -> l, t -> r );
        delete t; t = aux;
    }
    else {
        if( t -> l -> sz + 1 > p )
            t -> l = erase( t -> l, p );
        else
            t -> r = erase( t -> r, p - (t -> l -> sz + 1) );
    }

    t = update( t );
    return t;
}

T* rotate( T *t, int p ) {
    pair<T*, T*> aux = split( t, p );
    t = join( aux.second, aux.first );
    return t;
}

int find( T *t, int p ) {
    if( t == nil )
        return -1;

    if( t -> l -> sz + 1 == p )
        return t -> key;

    if( t -> l -> sz + 1 >= p )
        return find( t -> l, p );
    else
        return find( t -> r, p - (t -> l -> sz + 1) );
}

void dump( T *t ) {
    t = update( t );

    if( t == nil )
        return;

    dump( t -> l );
    out << t -> key << " ";
    dump( t -> r );

    t = update( t );
    return;
}

int main( int argc, const char *argv[] ) {

    srand( time(0) );
    r = nil = new T; r -> l = r -> r = nil;

    int n; in >> n;

    for( int i = 1; i <= n; i ++ )
        r = insert( r, i, i, abs( rand() ) % INT_MAX );

    for( int i = 1; i <= n; i ++ ) {
        int p = (i - 1) % (n - i + 1) + 1;

        if( i == 1 )
            p = 2;

        r = rotate( r, p - 1 );
        out << find( r, 1 ) << " ";
        r = erase( r, 1 );
    }


    return 0;
}