CF1876C.Autosynthesis

提高+/省选-

通过率:0%

时间限制:2.00s

内存限制:256MB

AC君温馨提醒

该题目为【codeforces】题库的题目,您提交的代码将被提交至codeforces进行远程评测,并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供,我们无法保证该服务的稳定性,若提交后无反应,请等待一段时间后再进行重试。

题目描述

Chaneka writes down an array aa of nn positive integer elements. Initially, all elements are not circled. In one operation, Chaneka can circle an element. It is possible to circle the same element more than once.

After doing all operations, Chaneka makes a sequence rr consisting of all uncircled elements of aa following the order of their indices.

Chaneka also makes another sequence pp such that its length is equal to the number of operations performed and pip_i is the index of the element that is circled in the ii-th operation.

Chaneka wants to do several operations such that sequence rr is equal to sequence pp. Help her achieve this, or report if it is impossible! Note that if there are multiple solutions, you can print any of them.

Chaneka 写下一个包含 nn 个正整数元素的数组 aa。初始时,所有元素均未被圈出。在一次操作中,Chaneka 可以圈出一个元素。同一个元素可以被多次圈出。

在完成所有操作后,Chaneka 构造序列 rr,它由数组 aa 中所有未被圈出的元素按其下标顺序组成。

Chaneka 还构造另一个序列 pp,其长度等于执行的操作次数,且 pip_i 表示第 ii 次操作中被圈出元素的下标。

Chaneka 希望执行若干次操作,使得序列 rr 等于序列 pp。请帮她实现这一目标,或判断这是不可能的!注意:若存在多种解法,输出任意一种即可。

输入格式

The first line contains a single integer nn (1≤n≤2⋅1051 \leq n \leq 2\cdot10^5) — the size of array aa.

The second line contains nn integers a1,a2,a3,…,ana_1,a_2,a_3,\ldots,a_n (1≤ai≤n1\leq a_i\leq n).

第一行包含一个整数 nn(1≤n≤2⋅1051 \leq n \leq 2\cdot10^5)—— 数组 aa 的大小。

第二行包含 nn 个整数 a1,a2,a3,…,ana_1,a_2,a_3,\ldots,a_n(1≤ai≤n1\leq a_i\leq n)。

输出格式

A single line containing −1-1 if it is impossible.

Otherwise, the output consists of two lines. The first line contains an integer zz representing the number of operations performed. The second line contains zz integers, the ii-th integer represents the index of the element circled in the ii-th operation. If there are multiple solutions, you can print any of them.

如果无法实现,则输出一行,包含 −1-1。

否则,输出包含两行。第一行包含一个整数 zz,表示执行的操作次数。第二行包含 zz 个整数,其中第 ii 个整数表示第 ii 次操作中被圈出的元素的索引。若存在多种解,输出任意一种即可。

输入输出样例

  • 输入#1

    5
    3 4 2 2 3

    输出#1

    3
    3 2 3
  • 输入#2

    3
    1 2 3

    输出#2

    -1

说明/提示

In the first example, doing the operations like the example output gives the following results:

  • Element a2a_2 gets circled 11 time.
  • Element a3a_3 gets circled 22 times.
  • The uncircled elements (ordered by their indices) are a1a_1, a4a_4, and a5a_5. So r=[3,2,3]r=[3,2,3].
  • p=[3,2,3]p=[3,2,3]

Therefore, r=pr=p.

In the second example, it is impossible.

在第一个例子中,按照示例输出所描述的操作,得到以下结果:

  • 元素 a2a_2 被圈出 11 次。
  • 元素 a3a_3 被圈出 22 次。
  • 未被圈出的元素(按其下标升序排列)为 a1a_1、a4a_4 和 a5a_5。因此 r=[3,2,3]r=[3,2,3]。
  • p=[3,2,3]p=[3,2,3]

因此,r=pr=p。

在第二个例子中,这是不可能的。

输入解题思路,AI测评打分。不知道怎么写?

首页