問題一覧 > 通常問題

No.2518 Adjacent Larger

レベル : / AI推定難易度 : 1275 / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : (AC するまで非表示) / 解いたユーザー数 111
作問者 : Shirotsume / テスター : MasKoaTS fky_
お気に入りにしたユーザー ProblemId : 10062 / 自分の提出
問題文最終更新日: 2023-10-25 16:29:16
This statement was translated by AI (claude-opus-5-5, effort medium) and may contain errors or differ in nuance from the original. The original statement takes precedence. Back to the original
yukicoder contest 410 (順位表) の他の問題:

Problem Statement

You are given a positive integer $N$ and a sequence of non-negative integers $A = (A_1, \dots, A_N)$ of length $N$.

Determine whether there exists a permutation $P$ of length $N$, obtained by rearranging $(1, \dots, N)$, that satisfies the following condition.

  • For every integer $i$ satisfying $1 \leq i \leq N$, the following holds.
    • The number of elements among $P_{i - 1}, P_{i + 1}$ that are greater than $P_i$ is $A_i$.

Here, $P_0$ refers to $P_N$, and $P_{N + 1}$ refers to $P_1$.

You are given $T$ test cases; solve each of them.

Constraints

  • All input values are integers.
  • $1 \leq T \leq 10^4$
  • $2 \leq N \leq 2 \times 10^5$
  • $0 \leq A_i \leq 2$
  • In a single input file, the sum of $N$ is at most $2 \times 10^5$.
  • Input

    The input is given from standard input. The first line contains the number of test cases $T$.

    $T$
    

    Then, each test case is given in the following format.

    $N$
    $A_1$ $\dots$ $A_N$
    

    Output

    For each test case, print Yes if a permutation $P$ satisfying the condition exists, and No otherwise.

    Sample

    Sample 1
    Input
    3
    4
    2 0 1 1
    4 
    2 2 0 0
    7
    1 1 1 1 1 1 1
    Output
    Yes
    No
    No

    There are 3 test cases.

    For the first test case, for example, $P = (1, 4, 3, 2)$ satisfies the condition in the problem statement. This can be verified as follows:

    • Among $P_0 = 2, P_2 = 4$, the number of elements greater than $P_1 = 1$ is $2$.
    • Among $P_1 = 1, P_3 = 3$, the number of elements greater than $P_2 = 4$ is $0$.
    • Among $P_2 = 4, P_4 = 2$, the number of elements greater than $P_3 = 3$ is $1$.
    • Among $P_3 = 3, P_5 = 1$, the number of elements greater than $P_4 = 2$ is $1$.

    Since a $P$ satisfying the condition exists, the answer is Yes.

    For the second and third test cases, no $P$ satisfying the condition exists. Therefore, the answer is No.

    提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。