CF1054C.Candies Distribution

普及/提高-

通过率:0%

时间限制:1.00s

内存限制:256MB

AC君温馨提醒

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

题目描述

There are nn children numbered from 11 to nn in a kindergarten. Kindergarten teacher gave aia_i (1≤ai≤n1 \leq a_i \leq n) candies to the ii-th child. Children were seated in a row in order from 11 to nn from left to right and started eating candies.

While the ii-th child was eating candies, he calculated two numbers lil_i and rir_i — the number of children seating to the left of him that got more candies than he and the number of children seating to the right of him that got more candies than he, respectively.

Formally, lil_i is the number of indices jj (1≤j<i1 \leq j \lt i), such that ai<aja_i \lt a_j and rir_i is the number of indices jj (i<j≤ni \lt j \leq n), such that ai<aja_i \lt a_j.

Each child told to the kindergarten teacher the numbers lil_i and rir_i that he calculated. Unfortunately, she forgot how many candies she has given to each child. So, she asks you for help: given the arrays ll and rr determine whether she could have given the candies to the children such that all children correctly calculated their values lil_i and rir_i, or some of them have definitely made a mistake. If it was possible, find any way how she could have done it.

幼儿园里有 nn 个孩子,编号从 11 到 nn。幼儿园老师给第 ii 个孩子分发了 aia_i(1≤ai≤n1 \leq a_i \leq n)颗糖果。孩子们按编号从左到右排成一排(即从 11 到 nn),并开始吃糖果。

当第 ii 个孩子在吃糖果时,他计算了两个数 lil_i 和 rir_i:其中 lil_i 表示坐在他左边且获得糖果数严格多于他的孩子人数;rir_i 表示坐在他右边且获得糖果数严格多于他的孩子人数。

形式化地,lil_i 是满足 1≤j<i1 \leq j < i 且 ai<aja_i < a_j 的下标 jj 的个数;rir_i 是满足 i<j≤ni < j \leq n 且 ai<aja_i < a_j 的下标 jj 的个数。

每个孩子都将自己算出的 lil_i 和 rir_i 告诉了老师。不幸的是,老师忘记了当初给每个孩子分发了多少颗糖果。因此,她请你帮忙:给定数组 ll 和 rr,判断是否存在一种糖果分配方案 a1,a2,…,ana_1, a_2, \dots, a_n,使得所有孩子均能正确计算出对应的 lil_i 和 rir_i;若不存在,则说明至少有一名孩子肯定算错了。如果存在这样的分配方案,请给出任意一种可行方案。

输入格式

On the first line there is a single integer nn (1≤n≤10001 \leq n \leq 1000) — the number of children in the kindergarten.

On the next line there are nn integers l1,l2,…,lnl_1, l_2, \ldots, l_n (0≤li≤n0 \leq l_i \leq n), separated by spaces.

On the next line, there are nn integer numbers r1,r2,…,rnr_1, r_2, \ldots, r_n (0≤ri≤n0 \leq r_i \leq n), separated by spaces.

第一行包含一个整数 nn(1≤n≤10001 \leq n \leq 1000)—— 幼儿园中儿童的数量。

第二行包含 nn 个整数 l1,l2,…,lnl_1, l_2, \ldots, l_n(0≤li≤n0 \leq l_i \leq n),以空格分隔。

第三行包含 nn 个整数 r1,r2,…,rnr_1, r_2, \ldots, r_n(0≤ri≤n0 \leq r_i \leq n),以空格分隔。

输出格式

If there is no way to distribute the candies to the children so that all of them calculated their numbers correctly, print «NO» (without quotes).

Otherwise, print «YES» (without quotes) on the first line. On the next line, print nn integers a1,a2,…,ana_1, a_2, \ldots, a_n, separated by spaces — the numbers of candies the children 1,2,…,n1, 2, \ldots, n received, respectively. Note that some of these numbers can be equal, but all numbers should satisfy the condition 1≤ai≤n1 \leq a_i \leq n. The number of children seating to the left of the ii-th child that got more candies than he should be equal to lil_i and the number of children seating to the right of the ii-th child that got more candies than he should be equal to rir_i. If there is more than one solution, find any of them.

如果不存在一种给孩子们分发糖果的方式,使得所有孩子都正确计算出了各自的数值,则输出 «NO»(不带引号)。

否则,在第一行输出 «YES»(不带引号)。在下一行输出 nn 个整数 a1,a2,…,ana_1, a_2, \ldots, a_n,以空格分隔——分别表示第 1,2,…,n1, 2, \ldots, n 个孩子获得的糖果数量。注意:这些数中可能有相等的,但所有数均需满足条件 1≤ai≤n1 \leq a_i \leq n。对于第 ii 个孩子,坐在他左侧且获得糖果数多于他的孩子数量应恰好等于 lil_i,坐在他右侧且获得糖果数多于他的孩子数量应恰好等于 rir_i。若存在多个解,输出任意一个即可。

输入输出样例

  • 输入#1

    5
    0 0 1 1 2
    2 0 1 0 0

    输出#1

    YES
    1 3 1 2 1
  • 输入#2

    4
    0 0 2 0
    1 1 1 1

    输出#2

    NO
  • 输入#3

    3
    0 0 0
    0 0 0

    输出#3

    YES
    1 1 1

说明/提示

In the first example, if the teacher distributed 11, 33, 11, 22, 11 candies to 11-st, 22-nd, 33-rd, 44-th, 55-th child, respectively, then all the values calculated by the children are correct. For example, the 55-th child was given 11 candy, to the left of him 22 children were given 11 candy, 11 child was given 22 candies and 11 child — 33 candies, so there are 22 children to the left of him that were given more candies than him.

In the second example it is impossible to distribute the candies, because the 44-th child made a mistake in calculating the value of r4r_4, because there are no children to the right of him, so r4r_4 should be equal to 00.

In the last example all children may have got the same number of candies, that's why all the numbers are 00. Note that each child should receive at least one candy.

在第一个例子中,如果老师分别向第 11、第 22、第 33、第 44、第 55 个孩子分发了 11、33、11、22、11 颗糖果,则所有孩子各自计算出的数值均正确。例如,第 55 个孩子得到了 11 颗糖果;他左侧有 22 个孩子各得到 11 颗糖果,11 个孩子得到 22 颗糖果,11 个孩子得到 33 颗糖果,因此他左侧共有 22 个孩子得到的糖果数多于他。

在第二个例子中,无法完成糖果分配,因为第 44 个孩子在计算 r4r_4 的值时出现了错误:他右侧没有任何孩子,因此 r4r_4 应等于 00。

在最后一个例子中,所有孩子可能都得到了相同数量的糖果,因此所有数值均为 00。注意:每个孩子至少应得到 11 颗糖果。

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

首页