На собрании
стояла довлеющая тишина. Стало окончательно ясно, что после битвы на Севере все
члены великого войска Коалиции закончат карьеру боевых магов и займут
руководящие должности Наставников. А значит, нужно срочно набирать новую боеспособную
армию. Лишь мудрый Сандро нарушал тишину скрипом пера о бумагу – он выписывал
имена достойных по его мнению кандидатов. Наконец, он закончил. На листке были
написаны 5n имён. Но суровые законы
предписывали выбрать лишь n
достойнейших магов. После долгих споров, было решено создать армию, в которой
каждая пара магов уважала бы друг друга.
Как известно, в
королевстве все маги живут в отдельных домах, расположенных в точках плоскости
с целыми координатами. Так получилось, что маги уважают друг друга в том и
только в том случае, если на отрезке, соединяющем их дома, лежит хотя бы одна
точка с целыми координатами, отличная от концов отрезка. Например, если дома
расположены в точках (1, 1) и (5, 5), то эти маги уважают друг друга, так как
между их домами есть точка (2, 2). А вот жильцы домов с координатами (0, 0) и
(1, 10), увы, не относятся друг к другу с уважением. Помогите правительству
королевства собрать армию!
Вход. В первой строке записано целое число n (1 ≤ n ≤
5000). В i-ой из следующих 5n строк записана пара целых чисел x и y,
по модулю не превосходящих 10000 – координаты дома i-го кандидата в армию. Все дома расположены в различных точках.
Выход. Если искомая
армия существует, в первой строке выведите "OK", а во второй строке
запишите через пробел в произвольном порядке n чисел – номера выбранных кандидатов. Если возможных ответов
несколько, выведите любой. Если армию создать нельзя, выведите "IMPOSSIBLE".
|
Пример
входа |
Пример
выхода |
|
2 1 1 5 5 0 0 2 2 0 10 6 6 7 7 8 8 9 9 10 10 |
OK 2 1 |
принцип
Дирихле
Заведем 4 урны:
первая урна хранит координаты (x, y) для которых обе координаты четные,
вторая – для которой x четно а y нечетно, в третьей урне x нечетно а y четно, в четвертой обе координаты нечетны. Сортировкой подсчетом
отсортируем координаты домов по урнам. Осталось найти урну, содержащую не менее
n координат (по принципу Дирихле
такая урна всегда будет существовать: у нас имеется 5n домов и 4 урны) и вывести ее произвольные n координат.
Жильцы любой
пары домов из одной урны всегда уважают друг друга, так как между ними всегда
существует точка с целочисленными координатами.
Для любого теста
ответ всегда существует.
Объявим массив урн для сортировки домов.
vector<int> m[2][2];
Читаем значение n. Сортируем дома по урнам.
scanf("%d",&n);
for(i = 1; i <= 5*n; i++)
{
scanf("%d
%d",&x,&y);
m[x & 1][y & 1].push_back(i);
}
Ищем, какая из урн содержит как минимум n домов.
if (m[0][0].size() >= n) x = 0, y =
0; else
if (m[0][1].size() >= n) x = 0, y =
1; else
if (m[1][0].size() >= n) x = 1, y =
0; else x = y = 1;
Выводим ответ – из урны (x,
y) выводим первые n координат.
printf("OK\n");
for(i = 0; i < n - 1; i++)
printf("%d
",m[x][y][i]);
printf("%d\n",m[x][y][n-1]);