题目详情题解（0）讨论（0）提交记录（0）

AT_abc362_c.[ABC362C] Sum = 0

普及-

通过率：0%

AC君温馨提醒

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

题目描述

给定 NN 个整数对 (L1,R1),(L2,R2),…,(LN,RN)(L_1, R_1), (L_2, R_2), \ldots, (L_N, R_N)。

请判断是否存在一个长度为 NN 的整数序列 X=(X1,X2,…,XN)X=(X_1, X_2, \ldots, X_N)，满足以下条件：

  • 对于每个 i=1,2,…,Ni=1,2,\ldots,N，都有 Li≤Xi≤RiL_i \leq X_i \leq R_i。
  • ∑i=1NXi=0\displaystyle\sum_{i=1}^N X_i = 0。

如果存在，请输出任意一个满足条件的序列。

输入格式

输入以如下格式从标准输入读入。

NN
L1L_1 R1R_1
L2L_2 R2R_2
⋮\vdots
LNL_N RNR_N

输出格式

如果不存在满足条件的序列，输出 No。

如果存在，输出 Yes，并在同一行输出满足条件的整数序列 X1 X2 … XNX_1\ X_2\ \ldots\ X_N。

如果有多个答案，输出任意一个均可。

输入输出样例

  • 输入#1

    3
3 5
-4 1
-2 3

    输出#1

    Yes
4 -3 -1

  • 输入#2

    3
1 2
1 2
1 2

    输出#2

    No

  • 输入#3

    6
-87 12
-60 -54
2 38
-76 6
87 96
-17 38

    输出#3

    Yes
-66 -57 31 -6 89 9

说明/提示

限制条件

  • 1≤N≤2×1051 \leq N \leq 2 \times 10^5
  • −109≤Li≤Ri≤109-10^9 \leq L_i \leq R_i \leq 10^9
  • 所有输入均为整数

样例解释 1

数列 X=(4,−3,−1)X=(4,-3,-1) 满足所有条件。其他如 (3,−3,0)(3,-3,0) 或 (5,−4,−1)(5,-4,-1) 也满足条件。

样例解释 2

不存在满足条件的整数序列 XX。

由 ChatGPT 4.1 翻译

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

首页