Тестування #27

Тестування (Editorial)

За умовою рівно одне число відрізняється за парністю від усіх інших. Отже, або в послідовності рівно одне непарне число, або рівно одне парне.

Звідси простий розв'язок у два проходи. Спочатку порахуємо кількість парних чисел та кількість непарних . Оскільки n \ge 3, рівно одна з цих величин дорівнює одиниці — саме вона і вказує на потрібну парність.

Другим проходом знайдемо позицію єдиного числа з цією парністю і виведемо її. Нумерація в задачі починається з одиниці, тому до індексу масиву треба додати .

Складність — , що з запасом вкладається в обмеження n \le 10^5. Зберігати всю послідовність не обов'язково: достатньо запам'ятати кількості чисел кожної парності та позиції першого парного і першого непарного.