#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; }
0 oznacza brak poprawnej odpowiedzi na jakiś test
pierwsza kolumna to suma czasów
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)
/*
* 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;
}
}