AT_arc198_c.[ARC198C] Error Swap

提高+/省选-

通过率:0%

AC君温馨提醒

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

题目描述

给定长度为 $ N $ 的两个整数序列 $ A=(A_1,A_2,\dots,A_N) $ 和 $ B=(B_1,B_2,\dots,B_N) $。

你可以执行以下操作最多 $ 31000 $ 次:

  • 选择满足 $ 1 \le i < j \le N $ 的整数对 $ (i,j) $,并将 $ A_i $ 替换为 $ A_j - 1 ,, A_j $ 替换为 $ A_i + 1 $。

你的目标是使 $ A = B $。判断目标是否可以实现,如果可以实现,请输出一个满足条件的操作序列。

输入格式

输入通过标准输入给出,格式如下:

$ N $
$ A_1\ A_2\ \dots\ A_N $
$ B_1\ B_2\ \dots\ B_N $

输出格式

如果可以使 $ A = B $,则输出 Yes,否则输出 No。

此外,如果输出 Yes,还需按照以下格式输出操作序列:

$ M $
$ i_1\ j_1 $
$ i_2\ j_2 $
$ \vdots $
$ i_M\ j_M $

其中,$ M $ 表示操作序列的长度,需满足 $ 0 \le M \le 31000 。。 i_k, j_k $ 表示第 $ k $ 次操作选择的 $ i, j $,需满足 $ 1 \le i_k < j_k \le N $。

如果存在多个解,输出任意一个均可。

输入输出样例

  • 输入#1

    4
    2 2 1 4
    3 2 2 2

    输出#1

    Yes
    2
    1 4
    3 4
  • 输入#2

    6
    5 4 4 3 4 2
    5 1 2 3 4 1

    输出#2

    No
  • 输入#3

    7
    2 4 2 4 3 2 5
    5 4 3 2 5 1 2

    输出#3

    Yes
    18
    5 7
    1 7
    2 4
    1 5
    1 5
    1 4
    4 5
    4 5
    3 4
    5 7
    1 5
    1 7
    1 6
    6 7
    1 7
    2 4
    2 5
    4 5

说明/提示

约束条件

  • $ 2 \le N \le 100 $
  • $ 1 \le A_i, B_i \le 100 $

样例解释 #1

通过以下操作可以使 $ A = B $:

  • 选择 $ (i,j) = (1,4) $,此时 $ A = (3,2,1,3) $。
  • 选择 $ (i,j) = (3,4) $,此时 $ A = (3,2,2,2) $。

由于不需要最小化操作次数,以下输出也是正确的:

Yes
6
1 4
3 4
1 2
1 2
1 2
1 2

翻译由 DeepSeek V3 完成

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

首页