сортировка за O(n)

[tori159]

Карточки с числами
ограничение по времени на тест1 секунда
ограничение по памяти на тест256 мегабайт
ввод input.txt
вывод output.txt

У Пети есть 2n карточек, на каждой из которых написано некоторое целое число. Числа на карточках могут совпадать. Пусть все карточки пронумерованы последовательными целыми числами от 1 до 2n. Число, записанное на карточке с номером i, обозначим как ai. Для того, чтобы сыграть с друзьями в одну увлекательную игру, Пете нужно разбить карточки на пары таким образом, чтобы в каждой паре числа на карточках были одинаковы. Помогите Пете это сделать.

Входные данные
В первой строке записано целое число n (1 ≤ n ≤ 3·105). Во второй строке записана последовательность из 2n положительных целых чисел a1, a2, ..., a2n (1 ≤ ai ≤ 5000) — числа, которые написаны на карточках. Числа в строке разделяются одиночными пробелами.

Выходные данные
Если невозможно разбить карточки на пары так, чтобы в каждой паре на карточках были написаны одинаковые числа, в единственной строке выведите число -1. Если же искомое разбиение существует, то выведите n пар чисел, по одной паре в строке — номера карточек, образующих пары.

Числа в парах разделяйте пробелами. Пары и числа в парах можно выводить в любом порядке. Если решений несколько, выведите любое из них.

[Poma][a]

В чем проблема?
Я бы создал массив p[1..5000], где p[i] есть список, содержащий номера карточек, значение которых равно i.
Дальше все супер просто. Бежим по массиву и ищем список, кол-во элементов в котором нечетно. Если такой имеется, пишем -1. Коли нет, выводим попарно все элементы p[i], где i in [1..5000]. Всё

[rrrFer]

То, что Ромаха описал называется сортировкой подсчетом. Более подробно можно у Скиены, например прочитать в "Алгоритмы и структуры данных".