CF814A.An abandoned sentiment from past

入门

通过率:0%

时间限制:1.00s

内存限制:256MB

AC君温馨提醒

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

题目描述

A few years ago, Hitagi encountered a giant crab, who stole the whole of her body weight. Ever since, she tried to avoid contact with others, for fear that this secret might be noticed.

To get rid of the oddity and recover her weight, a special integer sequence is needed. Hitagi's sequence has been broken for a long time, but now Kaiki provides an opportunity.

Hitagi's sequence a has a length of n. Lost elements in it are denoted by zeros. Kaiki provides another sequence b, whose length k equals the number of lost elements in a (i.e. the number of zeros). Hitagi is to replace each zero in a with an element from b so that each element in b should be used exactly once. Hitagi knows, however, that, apart from 0, no integer occurs in a and b more than once in total.

If the resulting sequence is not an increasing sequence, then it has the power to recover Hitagi from the oddity. You are to determine whether this is possible, or Kaiki's sequence is just another fake. In other words, you should detect whether it is possible to replace each zero in a with an integer from b so that each integer from b is used exactly once, and the resulting sequence is not increasing.

几年前,羽川翼遇到了一只巨大的螃蟹,它偷走了她全部的体重。自那以后,她一直避免与他人接触,生怕这个秘密被人发现。

为了摆脱这种异常状态并恢复体重,需要一个特殊的整数序列。羽川翼的序列已经损坏很久了,但如今火哀提供了机会。

羽川翼的序列 aa 长度为 nn。其中缺失的元素用 00 表示。火哀提供了另一个序列 bb,其长度 kk 等于 aa 中缺失元素的个数(即 aa 中 00 的个数)。羽川翼需将 aa 中每个 00 替换为 bb 中的一个元素,且 bb 中每个元素恰好使用一次。不过羽川翼知道:除 00 外,任意整数在整个 aa 和 bb 中至多只出现一次。

若最终得到的序列不是严格递增序列,则该序列便拥有使羽川翼摆脱异常状态的力量。你需要判断这种情况是否可能实现,还是说火哀提供的序列不过是又一个骗局。换句话说,你需要判断:是否存在一种方式,将 aa 中每个 00 替换为 bb 中的一个整数(bb 中每个整数恰好使用一次),使得最终序列不是严格递增的。

输入格式

The first line of input contains two space-separated positive integers n (2 ≤ n ≤ 100) and k (1 ≤ k ≤ n) — the lengths of sequence a and b respectively.

The second line contains n space-separated integers _a_1, _a_2, ..., a__n (0 ≤ a__i ≤ 200) — Hitagi's broken sequence with exactly k zero elements.

The third line contains k space-separated integers _b_1, _b_2, ..., b__k (1 ≤ b__i ≤ 200) — the elements to fill into Hitagi's sequence.

Input guarantees that apart from 0, no integer occurs in a and b more than once in total.

输入的第一行包含两个用空格分隔的正整数 nn(2 ≤ n ≤ 1002 \leq n \leq 100)和 kk(1 ≤ k ≤ n1 \leq k \leq n)——分别表示序列 aa 和 bb 的长度。

第二行包含 nn 个用空格分隔的整数 a1, a2, ..., ana_1, a_2, ..., a_n(0 ≤ ai ≤ 2000 \leq a_i \leq 200)——即 Hitagi 损坏的序列,其中恰好含有 kk 个零元素。

第三行包含 kk 个用空格分隔的整数 b1, b2, ..., bkb_1, b_2, ..., b_k(1 ≤ bi ≤ 2001 \leq b_i \leq 200)——需填入 Hitagi 序列中的元素。

输入保证:除 00 外,任意整数在 aa 和 bb 中总共至多出现一次。

输出格式

Output "Yes" if it's possible to replace zeros in a with elements in b and make the resulting sequence not increasing, and "No" otherwise.

如果可以用 b 中的元素替换 a 中的零,使得得到的序列不是递增的,则输出 "Yes";否则输出 "No"。

输入输出样例

  • 输入#1

    4 2
    11 0 0 14
    5 4

    输出#1

    Yes
  • 输入#2

    6 1
    2 3 0 8 9 10
    5

    输出#2

    No
  • 输入#3

    4 1
    8 94 0 4
    89

    输出#3

    Yes
  • 输入#4

    7 7
    0 0 0 0 0 0 0
    1 2 3 4 5 6 7

    输出#4

    Yes

说明/提示

In the first sample:

  • Sequence a is 11, 0, 0, 14.
  • Two of the elements are lost, and the candidates in b are 5 and 4.
  • There are two possible resulting sequences: 11, 5, 4, 14 and 11, 4, 5, 14, both of which fulfill the requirements. Thus the answer is "Yes".

In the second sample, the only possible resulting sequence is 2, 3, 5, 8, 9, 10, which is an increasing sequence and therefore invalid.

在第一个样例中:

  • 序列 aa 为 11, 0, 0, 1411,\,0,\,0,\,14。
  • 其中有两个元素丢失,而 bb 中的候选元素为 55 和 44。
  • 存在两种可能的最终序列:11, 5, 4, 1411,\,5,\,4,\,14 和 11, 4, 5, 1411,\,4,\,5,\,14,二者均满足要求。因此答案为 “Yes”。

在第二个样例中,唯一可能的最终序列为 2, 3, 5, 8, 9, 102,\,3,\,5,\,8,\,9,\,10,这是一个严格递增序列,因此不合法。

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

首页