AT_arc215_b.[ARC215B] Stolen Necklace

普及+/提高

通过率:0%

AC君温馨提醒

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

题目描述

有 2N2N 个宝石按从左到右排成一行,第 ii 个宝石的类型为 AiA_i。这里,AiA_i 是一个 11 到 NN 之间的整数,并且每种类型的宝石恰好有两个。

你需要插入若干分隔符,满足以下条件:

  • 每个分隔符的位置由整数 ii 表示(1≤i≤2N−11 \leq i \leq 2N-1),即分割在第 ii 个和第 (i+1)(i+1) 个宝石之间。
  • 同一位置不能有两个或更多分隔符。
  • 分隔符的数量 KK 不超过 NN。
  • 插入 KK 个分隔符后,宝石被分为 K+1K + 1 段。把所有奇数段(从左到右的第 1、3、5、……段)中的宝石取出来,恰好能得到每种类型 1,2,…,N1, 2, \ldots, N 的各一个宝石。

请输出一种满足条件的分隔符插入方式。可以证明一定存在这种分隔方式。

你将获得 TT 组测试数据。请解决每组数据。

输入格式

输入按下述格式从标准输入读入:

TT
case1\text{case}_1
case2\text{case}_2
⋮\vdots
caseT\text{case}_T

每组测试数据格式如下:

NN A1A_1 A2A_2 …\ldots A2NA_{2N}

输出格式

按顺序分别输出 TT 组测试数据的答案。

对于每组测试数据,输出一种满足条件的分隔符插入方式。具体来说,令 KK 为分隔符的数量,C1,C2,…,CKC_1, C_2, \ldots, C_K 表示分隔符的位置(严格递增),输出如下格式:

KK C1C_1 C2C_2 …\ldots CKC_K

这里 KK 必须不超过 NN。

输入输出样例

  • 输入#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,41, 2, 4 处,会把宝石分成如下各段 (1),(2),(2,3),(3,1)(1),(2),(2,3),(3,1),收集所有奇数段的宝石后,恰好得到每种类型 1,2,31,2,3 的各一个宝石。

约束条件

  • 1≤T≤1051 \leq T \leq 10^5
  • 1≤N≤2×1051 \leq N \leq 2\times 10^5
  • 1≤Ai≤N1 \leq A_i \leq N(1≤i≤2N1 \leq i \leq 2N)
  • 每种类型的宝石恰好有 2 个。即对于每个 xx(1≤x≤N1 \leq x \leq N),恰好存在两个下标 ii 满足 Ai=xA_i=x。
  • 所有测试数据的 NN 之和不超过 2×1052 \times 10^5。
  • 所有输入值均为整数。

由 ChatGPT 5 翻译

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

首页