Подарунки з чемпіонату (Розбір)

Задача на акуратне моделювання. Головне — помітити, що правила $2$ і $3$ насправді є одним і тим самим правилом, застосованим до різних розмірів.

Справді, для потрібного розміру ми спершу перевіряємо потрібний колір (правило $1$), а потім будь-який інший колір з найменшим номером (правило $2$). Для кожного наступного розміру — знову спочатку пріоритетний колір, а потім найменший номер (правила $3$ і $4$). Отже, весь пошук описується одним циклом:

для кожного розміру $j$, починаючи з потрібного і далі за зростанням:

 якщо є футболка потрібного кольору цього розміру — беремо її;

 інакше беремо футболку з найменшим номером кольору серед наявних цього розміру;

якщо жоден розмір не підійшов — записуємо пару (колір, розмір) як відсутню.

Розміри треба впорядкувати. Вони задані рядками (XS, S, M, L, XL, 2XL) і за умовою подаються за зростанням, тому достатньо зіставити кожному рядку його порядковий номер у вхідному рядку — зручно словником «назва $\to$ індекс».

Далі просто моделюємо запити в заданому порядку (це принципово: результат залежить від черговості) і зменшуємо лічильники на складі. Наприкінці виводимо дві таблиці n \times m: те, що залишилося, і те, чого не вистачило.

Про швидкодію. Прямий пошук найменшого доступного кольору сканує до n = 100 кольорів для кожного з m \le 6 розмірів, тобто до $600$ операцій на запит і до 6 \cdot 10^7 разом — це проходить, але на межі. Надійніше для кожного розміру $j$ тримати вказівник на найменший колір з ненульовим залишком і зсувати його вперед у міру вичерпання: кількості лише спадають, тому вказівник ніколи не рухається назад, і сумарна робота стає \mathcal{O}(nm + k).

Не забудьте, що «відсутньою» записується саме та футболка, яку просив учасник, а не та, яку шукали останньою.