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测评打分。不知道怎么写?

首页