====== AISD: pracownia C ======
  *{{:aisd:10.pracownia-c.pdf|Pracownia C}}.

===== Testy =====
  *{{:aisd:testy:testy-c.tar.bz2|Testy}} - testy jawne, test maksymalny.
===== Wyniki =====
http://www.ii.uni.wroc.pl/~mbi/dyd/aisd_10s/wyniki_C.html 

0 oznacza brak poprawnej odpowiedzi na jakiś test 

pierwsza kolumna to suma czasów
<code>
0:	Adr Dyli                                
0:	And Kaje
0:	Ani Stoz
0:	Dam Wiec
0:	Grz Kurd
0:	Jad Gruc
0:	Jak Sliw
0:	Kam Shai
0:	Luk Toma
0:	Mac Wiec
0:	Mar Mach
0:	Mic Roza
0:	Mic Soko
0:	Mik Ziem
0:	Pat Urba
0:	Paw Kime
0:	Pio Posa
0:	Sla Step
0:	m m (test)
472:	bi ff (test)
536:	Mik Kali
672:	Kon Wypy
708:	Pio Walk (test)
724:	Jak Tarn
748:	Ale Bali
752:	Daw Ryzn
776:	Pio Gajo
780:	Paw Kacp
780:	Pio Walk
784:	Dom Rusa
784:	Kam Miel
800:	Pio Rzep
820:	Mar Kacz
832:	Mac Maty
840:	Dom Rogo
852:	Mic Karp
856:	Mar Ocze
860:	Ada Kacz
860:	Kac Krol
888:	Bla Sala
928:	Krz Ziel
944:	Krz Nowi
960:	Mar Janc
972:	Mat Naha (test)
980:	Ada Wyzg
988:	Mac Pacu
1008:	Mat Naha
1020:	Paw Kici
1068:	Luk Zapa
1108:	Paw Kali
1128:	Mic Mazu
1144:	Wik Jana
1220:	Mar Kowa
1236:	Tom Losz (test)
1260:	Iza Bicz
1304:	Dan Blas
1304:	Fil Slom
1332:	Tom Losz
1376:	Krz Kusi
1412:	Pat Obar
1436:	Ada Czar
1440:	Luk Syno
1460:	Are Flin
1496:	Pio Bzow
1524:	Luc Fran
1588:	Mal Jurk
1748:	Mag Sara
1776:	Daw Jurc
1864:	Grz Chud
1896:	Mac Maty (test)
1948:	Dam Rusa
1992:	Pio Ryba
2184:	Mar Kola
2192:	Mar Janu
2200:	Kor Wegr
2220:	Dom Brul
2272:	Pio Krze
2388:	Dam Stra
2460:	Krz Parj
2532:	Krz Ziel (test)
2544:	Nha Nguy
2588:	Wal Augu (test)
2692:	Paw Muri
2752:	Joa Bieg
2904:	Paw Gawr (test)
2908:	Kar Kona
3020:	Pio Pole
3032:	Ale Gali
3276:	Szy Lasz
3344:	Raf Luka
3460:	Dam Piat
3720:	Mic Glen
3964:	Raf Kowa
4132:	Bar Krok
4260:	Daw Cies
4352:	Ada Kija
4888:	Luk Wrza
</code>
===== Rozwiązanie (biff) =====
<code>
#include <stdio.h>

#define MAX_SIZE 27000
typedef unsigned long long priority;

unsigned short size;
unsigned M, k, pushed_col;

struct Product
{   
    priority prio;
    unsigned x;
    unsigned y;
} elems[MAX_SIZE];                                                                                                                                                                                                                                                                             

#define L(n) ((n)<<1)
#define R(n) (((n)<<1)+1)
#define UP(n) ((n)>>1)
#define TOP (elems[0])

void heapify (unsigned short i)
{   
    rec:
    unsigned short bot = i;

    if (R (i) < size)
    {
        if (elems[R (i)].prio >= elems[i].prio)
            bot = (elems[L (i)].prio >= elems[R (i)].prio) ? L(i) : R(i);
        else if (elems[L (i)].prio >= elems[bot].prio)
            bot = L (i);
        else return;     
    }

    else if (L (i) == size - 1 && elems[L (i)].prio >= elems[bot].prio)
        bot = L (i);
    else return;

    if (bot != i) // TODO: niepotrzebne
    {
        Product tmp = elems[bot];
        elems[bot] = elems[i];
        elems[i] = tmp;

        i = bot;
        goto rec;
    }
}

inline void push (Product elem)
{
    unsigned short i = size;
    size += 1;

    // TODO: zmienic na switcha
    while ((i > 0) && elem.prio >= elems[UP (i)].prio)
    {
        elems[i] = elems[UP (i)];
        i = UP (i);
    }
    elems[i] = elem;
}

inline Product pop ()
{
    // assert(!HEAP_ISEMPTY(*h));
    Product max = elems[0];
    elems[0] = elems[--size];
    heapify (0);
    return max;
}


priority next ()
{
    Product p = TOP;
    priority xy = (priority) p.prio;
    unsigned mincol = p.x + p.y - 1;

    // zdejmij wszystkie o największym prioritecie
    while (size != 0 && TOP.prio == xy)
    {
        p = TOP;
        if (p.x + p.y < mincol)
            mincol = p.x + p.y - 1;
        (void) pop ();
    }

    // włóż kolejną przekątną
    if (mincol < pushed_col && mincol != 1)
    {
        unsigned x, y;
        pushed_col = mincol;

        x = mincol >> 1;
        y = x + (mincol % 2);

        priority xy1 = (priority) x * y;

        if (y <= M)
        {
            push ((Product) { xy1, x, y});

            while (y < M)
            {
                xy1 = xy1 + x - y - 1;
                x--; y++;
                if (xy1 < xy) // tylko mniejsze
                    push ((Product) { xy1, x, y});
                else
                    break;
            }
        }
    }

    return xy;
}

int main ()
{
    setvbuf (stdout, NULL, _IOFBF, 2 >> 15);

    char ch;

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

    push ((Product) { (priority) M * M, M, M});
    pushed_col = M + M;


    unsigned len;
    char out[14];
    out[13] = '\0';
    out[12] = '\n';

    unsigned long p1;
    priority p;

    while (k --> 0)
    {
        len = 11;
        p = next ();

        out[len--] = (p % 10) + '0';
        p1 = p / 10; // div dla ul jest szybsze niz dla ull

        while (p1 > 0)
        {
            out[len--] = (p1 % 10) + '0';
            p1 = p1 / 10;
        }

        fputs_unlocked (out + len + 1, stdout);
    }
}
</code>