====== AISD: pracownia F ======
{{:aisd:2010_f.pdf|}}

===== Testy =====
<file c generator.c>
#include <stdio.h>
#include <stdlib.h>
#include <time.h>

int cmp(const void *x, const void *y)
{
	return *(int*)x - *(int*)y;
}

int main(int argc, char **argv)
{
	srand(time(NULL));

	int n = rand() % 1000 + 1;
	int m = rand() % 1000 + 1;

	if(argc >= 3)
	{
		n = atoi(argv[1]);
		m = atoi(argv[2]);
	}

	int k = argc == 4 ? atoi(argv[3]) : rand() % 100000 + 1;

	printf("%d %d\n", n, m);
	for(int i = 0; i < n; i++)
	{
		for(int j = 0; j < m - 1; j++)
			printf("%d ", rand() % 1000000000 + 1);
		printf("%d\n", rand() % 1000000000 + 1);
	}

	int *tab = calloc(k, sizeof(k));

	for(int i = 0; i < k; i++)
		tab[i] = rand() % 1000000000 + 1;

	qsort(tab, k, sizeof(int), cmp);

	printf("%d\n", k);
	for(int i = 0; i < k - 1; i++)
		printf("%d ", tab[i]);
	printf("%d\n", tab[k - 1]);

	free(tab);

	return 0;
}
</file>
===== Wyniki =====
0 oznacza brak poprawnej odpowiedzi na jakiś test

pierwsza kolumna to suma czasów 
<code>
18292:  Jak Tarn
19596:  Mik Kali
19596:  Paw Muri
21480:  Pio Walk
21500:  Pio Krze
23624:  Sla Step
24212:  Mar Ocze
27020:  Pio Bzow
28296:  Dam Rusa
28636:  Kar Kona
28796:  Dam Stra
29584:  Pio Ryba
29612:  Pio Gajo
30028:  Mac Maty
30260:  Mar Kola
30800:  Mar Janu
34580:  Paw Kacp
35160:  Mic Karp
36428:  Pio Posa
37112:  Pio Rzep
37156:  Krz Ziel
38996:  Mic Soko
43140:  Wik Jana
43616:  Raf Kowa
49492:  Dom Brul
53132:  Paw Kali
0:      Dam Piat
0:      Dan Blas
0:      Dom Rusa
0:      Fil Slom
0:      Kac Krol
0:      Kon Wypy
0:      Krz Nowi
0:      Krz Parj
0:      Luk Syno
0:      Mac Maty (test)
0:      Mac Pacu
0:      Mac Wiec
0:      Mag Sara
0:      Mic Roza
0:      Paw Kime
0:      dzo busz (test) 
</code>

===== Rozwiązanie (2. czas) =====
<file=zadf.c>
/* 
 * Algorytm:
 * (a) wczytaj wszystkie pola do kolejki priorytetowej
 * (b) dopóki kolejka nie jest pusta
 *     (b1) zdejmij najwyższy element t
 *     (b2) sprawdź jego 4 sąsiadów. Jeżeli którykolwiek należy
 *          do jakiejś wyspy, dodaj t do tej wyspy. Jeżeli jest
 *          więcej niż 1 wyspa połącz te wyspy i dodaj do nich t.
 *          W przeciwnym przypadku stwórz jednoelementową wyspę.
 *     (b3) jeżeli szczyt kolejki priorytetowej jest niższy od t
 *          i kolejne zapytanie jest o wysokość t, wypisz ilość
 *          wysp.
 *
 * Wyspy są reprezentowane przez zbiory, dzięki czemu zapytania
 * o przynależność i łączenie wysp można wykonywać praktycznie
 * w czasie stałym.

 */

#include <stdio.h>
#include <alloca.h>
#include <stdlib.h>

#define READ_INT(a) a = 0; \
                    while ((ch = getchar_unlocked()) >= '0') \
                        a = a * 10 + (ch - '0');
char ch;

#define MAX_BOXEN (1024*1001)
#define MAX_QUESTIONS 100002

typedef struct Box {
    int height;
    short col;
    short row;
} Box;

#define coord(x,y) ((x)*1024+(y))

int BoxCmp(const void *x, const void *y)
    { return ((Box*)x)->height - ((Box*)y)->height; };

/* Union-Find */
int dad[MAX_BOXEN]; /*  0 - nie ma
                        1 - singleton
                        k - ma ojca k
                       -k - jest korzeniem rzędu k*/

int  Find   (int );
void Union  (int , int );
#define Insert(x)    (dad[x]=1)
#define SameSet(x,y) (Find(x)==(y))

int an_ind = 0; /* kolejne wolne pole; */
#define answers_push(x) (answers[an_ind++] = x)
#define answers_pop     (answers[--an_ind])
#define answers_empty   (an_ind == 0)

int qu_ind;
int qu_size;
#define questions_push(x) (questions[qu_ind--] = x)
#define questions_pop     (++qu_ind)
#define questions_top     (questions[qu_ind+1])
#define questions_empty   (qu_ind == qu_size)

int he_ind = 0;
#define heights_push(x) (heights[he_ind++]=x)
#define heights_pop     (heights[--he_ind])
#define heights_top     (heights[he_ind-1])
#define heights_empty   (he_ind == 0)

int main () {

setvbuf (stdout, NULL, _IOFBF, 2 << 5);
    short rows, // 1..1000
          cols; // 1..1000

    int islands = 0; // 0 .. 500000

    READ_INT (rows)
    READ_INT (cols)

    Box * heights = (Box *) alloca (sizeof (Box) * (cols*rows+1));

    Box b; // 1 .. 1 000 000 000
    for (b.row = 1; b.row <= rows; ++b.row)
    for (b.col = 1; b.col <= cols; ++b.col)
    {
        READ_INT (b.height)
        heights_push (b);
    }

    int nquestions; // 1 .. 100000
    READ_INT (nquestions)

    int * answers   = (int *)alloca(sizeof(int) * nquestions);
    int * questions = answers;
    qu_size = qu_ind = nquestions-1;

    qsort (heights, he_ind, sizeof (Box), BoxCmp);

    while (nquestions --> 0)
    {
        int q; // 1 .. 1 000 000 000
        READ_INT (q)

        if (q < heights_top.height)
            questions_push (q);
        else
        {
            do  /* każdego kolejnego dnia i tak wszystko będzie zalane */
                // scanf ("%d", & q);
                answers_push (0);
            while (nquestions --> 0);
            break;
        }
    }

    while (!heights_empty)
    {
        b = heights_pop;

        int o = coord (b.row,   b.col),
            n = coord (b.row-1, b.col),
            s = coord (b.row+1, b.col),
            e = coord (b.row,   b.col+1),
            w = coord (b.row,   b.col-1);
        int o1;

        Insert (o);
        islands++;

        /* dodaj/połącz wyspy */
        if ((b.row-1>0)     && (n = Find (n)))
            { Union (o,n); islands--; }

        if ((b.row+1<=rows) && (s = Find (s)) && ((o1 = Find(o)) != s))
            { Union (o1,s); islands--; }

        if ((b.col-1>0)     && (w = Find (w)) && ((o1 = Find(o)) != w))
            { Union (o1,w); islands--; }

        if ((b.col+1<=cols) && (e = Find (e)) && ((o1 = Find(o)) != e))
            { Union (o1,e); islands--; }

        /* kolejny/ostatni dzień */
        if (heights_empty || (heights_top.height != b.height))
        {
            /* dopóki nie wynurzą się kolejne pola */
            while (!questions_empty && questions_top >= heights_top.height)
            {
                questions_pop;
                answers_push (islands);
            }
            if (questions_empty) goto done;
        }
    }

done:

    /* już wszystko jest nad powierzchnią wody */
    while (!questions_empty)
    {
        questions_pop;
        answers_push (1);
    }

    unsigned len;
    char out[8];
    out[7] = '\0';

    if (!answers_empty) printf ("%d", answers_pop);
    while (!answers_empty)
    {
        int num = answers_pop;

        len = 6;

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

        out[len] = ' ';

        fputs_unlocked (out + len, stdout);
    }

    return 0;
}


inline int Find (int  i)
{
    int root = i,
        temp;

    if (dad[i] == 0) return 0;  // nie ma
    else
    if (dad[i] == 1) return i;  // jest singletonem

    /* znajdź i - reprezentanta zbioru (zawsze ten sam) */
    while (dad[root] > 1)
        root = dad[root];

    /* Wszystkie odwiedzone wierzchołki mogą wskazywać na i */
    while (dad[i] > 1) {
        temp      = i;
        i         = dad[i];
        dad[temp] = root;
    }

    return root;
}

inline void Union (int i, int j)
{
    // assert (i != j)

    /* płytsze drzewo jest poddrzewem głębszego
     * mniejsze wartości dad[root] reprezentują głębsze drzewa.
     * -1 to korzeń */

    if (dad[j] > dad[i]) {
        dad[i] += -1 + dad[j];
        dad[j]  = i;
    } else {
        dad[j] += -1 + dad[i];
        dad[i]  = j;
    }
}
</file>