====== AISD: pracownia E ======
  *{{:aisd:10.pracownia-e.pdf|Pracownia E}}.

===== Testy =====
  *{{:aisd:testy:testy-e.tar.bz2|Testy E}}.

  * testy są w /home/i221141/e na herze (testy-e.tar.bz2 zawiera wszystkie testy i odpowiedzi, można również uruchomić na rozpakowanych)

Czasy (**na herze**) dla struktur danych (wszystkie testy odpalone sprawdzarką dude'a):

^ Struktura ^ Czas ^
| RBT (drx, c++) | 25.81 s |
| SkipList (ekg2, C) | 29.09 s |
| AVL (dude, C) | 32 s |
| AVL (tr) | 32.98 s |

Ja mam na RBT i działa szybko. Podejrzewam, że AVL działałyby podobnie szybko (AVL mają wysokość <1.44log(n) vs <2log(n) RBT; mają więc szybszy Upper i Lower, ale wolniejszy Insert i Delete) jeśli rozkład I+U jest podobny jak U+L, co zależy od testów.

Swoją drogą ciekawią mnie [[http://en.wikipedia.org/wiki/Van_Emde_Boas_tree|drzewa van Emde Boasa]], które mają operacje słownikowe w $O(log log n)$. Co prawda ilość elementów jest mała -- maksymalnie 50000; log(50000) = 15.6, ale log(36) = 5.2, więc drzewa vEB mogą być nawet sześć razy szybsze. --- //[[drx@drx.pl|drx]] 2010/05/23 18:16//

Moje (dj3500) i Damiana czasy, testowane za pomocą:
<code>time for i in `seq 1 10`; do ./program < test$i.in > test$i.tempout; done</code>
^ Struktura ^ Czas ^
| Treap (dj3500, c++) | 27.31 s |
| Splay (DS, c++) | 39.34 s |
| RBT z STLa (dj3500, c++) | 28.04 s |
| trwałe RBT (dj3500, ocaml, dostaje głównie TLE, wyłazi też poza 4MB) | 61.24 s |
Warto też może nadmienić, że treap ma 102 linijki, a cały program 3.5 kB kodu więc jeśli nie widać różnicy to po co przepłacać ;)
//dj3500//

===== Wyniki =====
[[http://www.ii.uni.wroc.pl/~mbi/dyd/aisd_10s/wyniki_E.html]] - wyniki

0 oznacza brak poprawnej odpowiedzi na jakiś test

pierwsza kolumna to suma czasów 
<code>
11304:  Mik Kali
13336:  Kon Wypy
13492:  Luk Syno
14248:  Luk Zapa
14272:  Pio Pole
14444:  Krz Kusi
14484:  Daw Jurc
14620:  Mar Ocze
14824:  Mic Karp
15028:  Wik Jana
15060:  Mag Sara
15128:  Kac Krol
15188:  And Kaje
15204:  Pio Bzow
15260:  Paw Muri
15460:  Dam Rusa
15500:  Krz Parj
15696:  Krz Ziel (test)
15716:  Kar Kona
15848:  Jak Tarn
15960:  Pio Posa
16008:  Mar Kola
16100:  Dam Stra
16160:  Pio Krze
16312:  Pio Ryba
16408:  Dan Blas
16828:  Krz Nowi
16884:  Krz Ziel
17036:  Iza Bicz
17440:  Mar Janu
17468:  Pio Rzep
17936:  Mic Mazu
18008:  Adr Dyli
18052:  Paw Kacp
18408:  Pio Gajo
18660:  Mic Roza
19072:  Pio Walk
19932:  Mac Maty
26812:  Mic Soko
0:  Ark Goch
0:  Raf Kowa
0:  Mic Kras
0:  Dam Piąt
0:  Mac Wiec
0:  Ada Kacz
0:  Ale Gali
0:  Bla Sala
0:  Dam Wiec
0:  Dom Brul
0:  Dom Rusa
0:  Fil Slom
0:  J L (test)
0:  Kam Miel
0:  Luc Fran
0:  Luk Toma
0:  Luk Wrza
0:  Mac Pacu
0:  Mar Janc
0:  Pat Urba
0:  Paw Kali
0:  Paw Kime
0:  Sla Step
0:  Szy Lasz
0:  Tom Luch
0:  Wal Augu (test)
</code>

===== Rozwiązanie (1. czas) =====

<file zad5.c>
#include <stdio.h>

#define SEARCH_BRAK (2LL<<60)
#define MAX_ELEMS 50010
#define LMAX 1000000000L

typedef signed long long T;

inline void putll (T & x) 
{
    signed long l = x / LMAX,
                r = x % LMAX;
    
    if (l != 0)
        printf("%ld%09ld\n", l,(r<0)?-r:r);
    else 
        printf("%ld\n", r);
}

typedef struct node
{
    T data;
    int prio;
    struct node *left, *right, *up;
} node;

node * root; 


/* Własny alokator pamięci. */
unsigned short nextFreeBlock[MAX_ELEMS]; // następna wolna komórka za bieżącą wolną (0 to kolejna)
node Block[MAX_ELEMS]; // pula pamięci

unsigned short firstFreeBlock = 1;	// bo zero to specjalna wartosc
unsigned int index;

#define allocate(X) X = &Block[firstFreeBlock]; \
                    if (nextFreeBlock[firstFreeBlock] == 0) \
                        firstFreeBlock++; \
                    else \
                        firstFreeBlock = nextFreeBlock[firstFreeBlock];

#define free(X) index = X - &Block[0]; \
                nextFreeBlock[index] = firstFreeBlock; \
                firstFreeBlock = index; 
/****/

inline void rotate_left (node * n)
{
    node *x = n->right;

    x->up = n->up;
    if (x->up != NULL)
    {
        if (x->up->left == n)
            x->up->left = x;
        else
            x->up->right = x;
    }

    n->right = x->left;
    if (n->right != NULL)
        n->right->up = n;

    n->up = x;
    x->left = n;
}

inline void rotate_right (node * n)
{
    node *x = n->left;

    x->up = n->up;
    if (x->up != NULL)
    {
        if (x->up->left == n)
            x->up->left = x;
        else
            x->up->right = x;
    }

    n->left = x->right;
    
    if (n->left != NULL)
        n->left->up = n;

    n->up = x;
    x->right = n;
}

void ins (T & e)
{
    T ret = 0;
    node *n = root,
         *p = NULL;

    static int next = 1;  

    // p - ojciec e
    while (n != NULL)
    {
        p = n;
        ret = e - (n->data);

        if (ret < 0)
            n = n->left;
        else if (ret > 0)
            n = n->right;
        else
            return;	// duplikat
    }

    allocate(n);

    n->left = n->right = NULL;
    n->up = p;
    n->data = e;

    if (p == NULL)
        root = n;
    else if (ret < 0)
        p->left = n;
    else
        p->right = n;

    next = next * 1103515245 + 12345;
    n->prio = (unsigned)(next/65536) % 32768;

    // rebalance 
    while (n->up != NULL && 
          (n->up->prio) > (n->prio))

        if (n->up->right == n)
            rotate_left (n->up);
        else
            rotate_right (n->up);

    if (n->up == NULL)
        root = n;

}

void del (T & e)
{
    node *n = NULL,
         *m = root;

    // znajdź poprzednika e - n.
    while (m != NULL)
        if (e < m->data)
            m = m->left;
        else
        {
            n = m;
            m = m ->right;
        }


    if ((n == NULL) || (n->data != e))
    {
        fputs_unlocked ("BRAK\n", stdout);
        return;
    }

    /* rotuj do liścia */
    while (n->left != NULL || n->right != NULL)
    {
        if (n->left != NULL)
        {
            if (n->right == NULL || n->left->prio < n->right->prio)
                rotate_right (n);
            else
                rotate_left (n);
        }
        else
            rotate_left (n);

        if (root == n)
            root = n->up;
    }

    if (n->up == NULL)
        root = NULL;
    else
        if (n->up->left == n)
            n->up->left = NULL;
        else
            n->up->right = NULL;

    free(n);

    fputs_unlocked ("OK\n", stdout);
}

inline void lower (node * t, T & k)
{
    T ret = SEARCH_BRAK;

    while (t != NULL)
    {
        if (t->data == k) {
            putll (k);
            return; 
        }

        if (k < t->data)
            t = t->left;
        else
        {
            ret = t->data;
            t   = t->right;
        }
    }

    if (ret == SEARCH_BRAK)
        fputs_unlocked ("BRAK\n", stdout);
    else
        putll ( ret);

}

inline void upper (node * t, T & k)
{
    T ret = SEARCH_BRAK;

    while (t != NULL)
    {
        if (t->data == k) 
        {
            putll ( k);
            return;
        }

        if (k < t->data)
        {
            ret = t->data;
            t = t->left;
        }
        else
            t = t->right;
    }

    if (ret == SEARCH_BRAK)
        fputs_unlocked ("BRAK\n", stdout);
    else
        putll ( ret);
}


int main (void)
{
    setvbuf (stdout, NULL, _IOFBF, 2 << 10);

    T sign, n;
    char op, ch;
    int oper;

    root = NULL;

    oper = getchar_unlocked() - '0';  
    while ((ch = getchar_unlocked ()) >= '0')
        oper = oper * 10 + (ch - '0');

    while (oper --> 0)
    {
        sign = 1;
        n = 0;

        op = getchar_unlocked ();	// operacja
        getchar_unlocked ();	    // spacja

        ch = getchar_unlocked ();
        if (ch == '-')
            sign = -1;
        else
            n = ch - '0';

        while ((ch = getchar_unlocked ()) >= '0')
            n = n * 10 + (ch - '0');

        n *= sign; 

        switch (op)
        {
            case 'I': ins (n);         break;
            case 'D': del (n);         break;
            case 'L': lower (root, n); break;
            default:  upper (root, n);
        }
    }

    return 0;
}
</file>