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
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
#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);
}
}
Dyskusja
Że co?