AT_arc179_a.[ARC179A] Partition

普及-

通过率:0%

AC君温馨提醒

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

题目描述

给定你整数 NN 和 KK。

定义长度为 NN 的整数序列 X=(X1,X2,…,XN)X=(X_1,X_2,\dots,X_N) 的前缀和为长度为 N+1N+1 的序列 Y=(Y0,Y1,…,YN)Y=(Y_0,Y_1,\dots,Y_N) 满足:

  • Y0=0Y_0=0

  • Yi=∑j=1iXj(i=1,2,…,N)Y_i=\sum\limits_{j=1}^{i}X_j (i=1,2,\dots,N)

如果一个长度为 NN 的整数序列 X=(X1,X2,…,XN)X=(X_1,X_2,\dots,X_N) 满足以下条件,那么它被成为好的序列:

  • 在 XX 的前缀和中,任何小于 KK 的值都出现在任何不小于 KK 的值之前。
    • 形式化的说,对于 XX 的前缀和 YY,对于任意整数对 (i,j)(i,j) 其中 0≤i,j≤N0\le i,j\le N,如果 Yi<KY_i<K 且 Yj≥KY_j\ge K 那么 i<ji<j。

给你一个长度为 NN 的整数序列 A=(A1,A2,…,AN)A=(A_1,A_2,\dots,A_N)。判断是否能够通过重排 AA 中的元素使 AA 变成一个好的序列。如果可以,输出重排后的结果。

输入格式

第一行,输入两个整数 N,KN,K。

第二行,输入 NN 个整数,表示数列 AA。

输出格式

如果能够通过重排 AA 使得 AA 变成一个好的序列,那么:

第一行,输出 Yes。

第二行,输出 NN 个整数,表示重排过后的序列 AA。

如果有多个满足条件的重排后的序列,输出任意一个都会被视为是正确的。

如果无法通过重排 AA 使得 AA 变成一个好的序列,输出 No。

样例 1 解释

如果将 AA 重排为 (−3,−1,2,4)(-3,-1,2,4),那么 AA 的前缀和 YY 为 (0,−3,−4,−2,2)(0,-3,-4,-2,2)。在 YY 中任何小于 11 的值都会出现在任何不小于 11 的值之前。

输入输出样例

  • 输入#1

    4 1
    -1 2 -3 4

    输出#1

    Yes
    -3 -1 2 4
  • 输入#2

    4 -1
    1 -2 3 -4

    输出#2

    No
  • 输入#3

    10 1000000000
    -1000000000 -1000000000 -1000000000 -1000000000 -1000000000 1000000000 1000000000 1000000000 1000000000 1000000000

    输出#3

    Yes
    -1000000000 -1000000000 -1000000000 -1000000000 -1000000000 1000000000 1000000000 1000000000 1000000000 1000000000

说明/提示

  • 1≤N≤2×1051\le N\le 2\times 10^5;
  • −109≤K≤109-10^9\le K\le 10^9;
  • −109≤Ai≤109-10^9\le A_i\le 10^9;
  • 所有输入都是整数。

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

首页