#include #include #include #define MAXN 1048576 #define MAXG 1048576 #define MAXB 1024 static unsigned req[MAXN]; static unsigned next[MAXN]; static unsigned bay[MAXG]; static unsigned n, g, b; __inline__ static void gennext (void) { static unsigned np[MAXG]; size_t i; memset (np, 0xFF, g * sizeof (*np)); i = n - 1; do { next[i] = np[req[i]]; np[req[i]] = i; } while (i-- != 0); } struct he { unsigned pos; unsigned next; }; static struct he heap[MAXB + 1]; size_t heap_end; __inline__ static void heap_init (void) { size_t i; for (i = 1; i <= b; i++) { heap[i].pos = i - 1; heap[i].next = UINT_MAX; } heap_end = b; } __inline__ static size_t heap_get (void) { size_t dest, res; res = heap[1].pos; dest = 1; while (2 * dest <= heap_end) { size_t less; less = 2 * dest; if (2 * dest < heap_end && heap[2 * dest].next < heap[2 * dest + 1].next) less++; if (heap[less].next > heap[heap_end].next) break; heap[dest] = heap[less]; dest = less; } heap[dest] = heap[heap_end]; heap_end--; return res; } __inline__ static void heap_add (size_t pos, size_t next) { size_t dest; heap_end++; dest = heap_end; while (dest > 1 && heap[dest / 2].next < next) { heap[dest] = heap[dest / 2]; dest /= 2; } heap[dest].pos = pos; heap[dest].next = next; } int main (void) { unsigned test, tn; scanf ("%u", &test); for (tn = 1; tn <= test; tn++) { static size_t bg[MAXB]; size_t i; printf ("Case %u:\n", tn); scanf ("%u%u%u", &b, &g, &n); for (i = 0; i < n; i++) { scanf ("%u", req + i); req[i]--; } gennext (); memset (bay, 0xFF, g * sizeof (*bay)); memset (bg, 0xFF, b * sizeof (*bg)); heap_init (); for (i = 0; i < n; i++) { if (bay[req[i]] != UINT_MAX) printf ("NO ACTION\n"); else { size_t pos; pos = heap_get (); if (bg[pos] != UINT_MAX) bay[bg[pos]] = UINT_MAX; bay[req[i]] = pos; bg[pos] = req[i]; printf ("LOAD %u %u\n", pos + 1, req[i] + 1); heap_add (pos, next[i]); } } if (tn != test) putchar ('\n'); } return EXIT_SUCCESS; }