AT_agc058_a.[AGC058A] Make it Zigzag
普及+/提高
通过率:0%
AC君温馨提醒
该题目为【atcoder】题库的题目,您提交的代码将被提交至atcoder进行远程评测,并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供,我们无法保证该服务的稳定性,若提交后无反应,请等待一段时间后再进行重试。
题目描述
给定一个排列 $ P=(P_1,P_2,\cdots,P_{2N}) $,其中 $ (1,2,\cdots,2N) $。
你可以进行以下操作 $ 0 $ 到 $ N $ 次:
- 选择一个整数 $ x $ ($ 1\ \leq\ x\ \leq\ 2N-1 $),交换 $ P_x $ 和 $ P_{x+1} $ 的值。
请找出一系列操作,使得操作后的 $ P $ 满足以下条件:
- 对于每个 $ i=1,3,5,\cdots,2N-1 , P_i\ <\ P_{i+1} $。
- 对于每个 $ i=2,4,6,\cdots,2N-2 , P_i\ >\ P_{i+1} $。
请输出满足条件的一系列操作,以以下形式输出:
$ K $ $ x_1 $ $ x_2 $ $ \cdots $ $ x_K $
其中,$ K $ 表示操作次数 ($ 0\ \leq\ K\ \leq\ N ), x_i $ ($ 1\ \leq\ x_i\ \leq\ 2N-1 $) 表示第 $ i $ 次操作选择的 $ x $ 的值。如果存在多个满足条件的解,任意输出一个即可。
输入格式
从标准输入中按以下格式给出输入:
$ N $ $ P_1 $ $ P_2 $ $ \cdots $ $ P_{2N} $
输出格式
按以下格式输出操作序列:
$ K $ $ x_1 $ $ x_2 $ $ \cdots $ $ x_K $
样例 #1
样例输入 #1
2
4 3 2 1
样例输出 #1
2
1 3
样例 #2
样例输入 #2
1
1 2
样例输出 #2
0
输入输出样例
输入#1
2 4 3 2 1
输出#1
2 1 3
输入#2
1 1 2
输出#2
0
说明/提示
约束条件
- $ 1\ \leq\ N\ \leq\ 10^5 $
- $ (P_1,P_2,\cdots,P_{2N}) $ 是 $ (1,2,\cdots,{2N}) $ 的排列
- 输入的数值均为整数
样例解释 1
将 $ P=(4,3,2,1) $ 根据操作后,得到 $ P=(3,4,1,2)$,满足条件。
输入解题思路,AI测评打分。不知道怎么写?