AT_arc215_b.[ARC215B] Stolen Necklace
普及+/提高
通过率:0%
AC君温馨提醒
该题目为【atcoder】题库的题目,您提交的代码将被提交至atcoder进行远程评测,并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供,我们无法保证该服务的稳定性,若提交后无反应,请等待一段时间后再进行重试。
题目描述
有 2N 个宝石按从左到右排成一行,第 i 个宝石的类型为 Ai。这里,Ai 是一个 1 到 N 之间的整数,并且每种类型的宝石恰好有两个。
你需要插入若干分隔符,满足以下条件:
- 每个分隔符的位置由整数 i 表示(1≤i≤2N−1),即分割在第 i 个和第 (i+1) 个宝石之间。
- 同一位置不能有两个或更多分隔符。
- 分隔符的数量 K 不超过 N。
- 插入 K 个分隔符后,宝石被分为 K+1 段。把所有奇数段(从左到右的第 1、3、5、……段)中的宝石取出来,恰好能得到每种类型 1,2,…,N 的各一个宝石。
请输出一种满足条件的分隔符插入方式。可以证明一定存在这种分隔方式。
你将获得 T 组测试数据。请解决每组数据。
输入格式
输入按下述格式从标准输入读入:
T
case1
case2
⋮
caseT
每组测试数据格式如下:
N A1 A2 … A2N
输出格式
按顺序分别输出 T 组测试数据的答案。
对于每组测试数据,输出一种满足条件的分隔符插入方式。具体来说,令 K 为分隔符的数量,C1,C2,…,CK 表示分隔符的位置(严格递增),输出如下格式:
K C1 C2 … CK
这里 K 必须不超过 N。
输入输出样例
输入#1
2 3 1 2 2 3 3 1 5 1 2 3 4 5 5 4 3 2 1
输出#1
3 1 2 4 1 5
说明/提示
样例解释 1
对于第一组数据,把分隔符插在 1,2,4 处,会把宝石分成如下各段 (1),(2),(2,3),(3,1),收集所有奇数段的宝石后,恰好得到每种类型 1,2,3 的各一个宝石。
约束条件
- 1≤T≤105
- 1≤N≤2×105
- 1≤Ai≤N(1≤i≤2N)
- 每种类型的宝石恰好有 2 个。即对于每个 x(1≤x≤N),恰好存在两个下标 i 满足 Ai=x。
- 所有测试数据的 N 之和不超过 2×105。
- 所有输入值均为整数。
由 ChatGPT 5 翻译
输入解题思路,AI测评打分。不知道怎么写?