Memory training#184

Memory training (Editorial)

Кожен наступний масив — це попередній без рівно одного елемента. Тому достатньо для кожної сусідньої пари масивів знайти, яке число зникло.

Оскільки числа можуть повторюватися, порівнювати треба мультимножини, а не множини. Найпростіше: для попереднього масиву побудувати словник «значення $\to$ кількість», потім пройтися новим масивом і зменшувати відповідні лічильники. Значення, у якого лічильник залишиться додатним, і є забраним числом.

Ходи чергуються: перший забирає Василь, другий — Петро, третій знову Василь і так далі. Тобто на кроці $k$ (нумерація з одиниці) число дістається Василю при непарному $k$ і Петру при парному.

Важлива деталь: усього ходів $n$ , а масивів у вхідних даних лише $n - 1$ n - 1 (початковий плюс $n - 1$ n-1 проміжних). Останній названий масив містить рівно один елемент — це число, яке ще не забрали, і воно дістається тому, чия черга ходити останньою. Простіше кажучи, після обробки всіх пар залишиться одне неврахований елемент; віддайте його гравцеві, чий хід за номером $n$ .

Наприкінці відсортуйте обидва списки за неспаданням і виведіть.

Оскільки $n \leq 1000$ n \le 1000, сумарний розмір усіх масивів становить близько $n^{2} /2 \approx 5 \cdot 1 0^{5}$ n^2/2 \approx 5 \cdot 10^5 чисел, тому підхід зі словником для кожної пари цілком укладається в обмеження.

n - 1

n - 1

n \leq 1000

n^{2} /2 \approx 5 \cdot 1 0^{5}