Задача «Тапкодёр» РОИ 2008 Автор задачи: Елена Владимировна Андреева Разбор: Елена Владимировна Андреева
i- й и j- й игроки встречаются в туре с номером старший бит в числе (i-1) xor (j-1)
Храним в массиве список уже выбывших участников Рассмотрим все договорные матчи очередного тура Рассмотрим конкретного участника этих матчей 1) он выигрывает хотя бы один матч и его соперник мог дойти до этого тура 2) у него только p проигрышных матчей и всего q человек могут с ним играть он вылетает при p = q (p < q выигрывает)
В i-м туре участвует 2 i человек, если 2 i > N, то больше никто выбыть не сможет
Структуры данных Отсортированный массив претендентов Отсортированный по номерам массив для выбывших Отсортированный по турам массив договорных матчей