12046. Чи телефонували?


Відправити розв'язок

Бали: 100
Time limit: 2.0s
Memory limit: 500M

Authors:
Problem type
Allowed languages
C++, Java, Pascal, Python

Є \(N\) осіб, ідентифікатори яких дорівнюють \(1, 2, … N\). Кожна особа \(i\) виконує таку дію один раз у такому порядку:

  • Якщо ідентифікатор особи \(i\) ще не викликано, зателефонуйте ID особи \(A_i\).

Перелічіть ідентифікатори всіх людей, чиї ідентифікатори ніколи не викликалися до кінця в порядку зростання.

Обмеження

  • \(2≤N≤2×10^5\)
  • \(1≤A_i ​ ≤N\)
  • \(A_i ​ \neq i\)
  • Усі значення у вхідних даних є цілими числами.

Формат вхідних даних

Перший рядок містить ціле число \(N\).

Наступний   рядок містить цілі числа \(A_i\).

Формат вихідних даних

Перелічіть ідентифікатори всіх людей, чиї ідентифікатори не викликані до кінця, у порядку зростання у такому форматі:

\(K\)

\(X_1\) ​ \(X_2\) ​ … \(X_K\) ​

Іншими словами, перший рядок має містити кількість людей \(K\), чиї Ідентифікатори ніколи не викликаються до кінця;

другий рядок має містити послідовність \((X_1 ​ , X_2 ​ ,…, X_K ​ )\) ідентифікаторів таких людей у порядку зростання з пробілами між ними.

Приклад вхідних даних

5
3 1 4 5 4

Приклад вихідних даних

2
2 4

Дії п'яти людей такі.

  • Ідентифікатор особи 1 ще не озвучений, тому особа 1 називає ідентифікатор особи 3.
  • Ідентифікатор особи 2 ще не був названий, тому особа 2 викликає ідентифікатор особи 1.
  • Особа 1 вже озвучила ідентифікатор особи 3, тому нічого не відбувається.
  • Ідентифікатор особи 4 ще не був названий, тому особа 4 називає ідентифікатор особи 5.
  • Особа 4 вже озвучила ідентифікатор особи 5, тому нічого не відбувається.

Тому ідентифікатори осіб 2 і 4 не викликаються до кінця.

Приклад вхідних даних

20
9 7 19 7 10 4 13 9 4 8 10 15 16 3 18 19 12 13 2 12

Приклад вихідних даних

10
1 2 5 6 8 11 14 17 18 20

Коментарі

Ще немає коментарів.