| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 4 초 | 1024 MB | 3 | 2 | 2 | 66.667% |
For two sequences $x$ and $y,ドル we define $\text{LCS}(x, y)$ as the length of their longest common subsequence.
You are given 4ドル$ integers $n,ドル $a,ドル $b,ドル $c$. Determine if there exist 3ドル$ permutations $p,ドル $q,ドル $r$ of integers from 1ドル$ to $n,ドル such that:
If such permutations exist, find any such triple of permutations.
A permutation $p$ of integers from 1ドル$ to $n$ is a sequence of length $n$ such that all elements are distinct integers in the range $[1,n]$. For example, $(2, 4, 3, 5, 1)$ is a permutation of integers from 1ドル$ to 5ドル$ while $(1, 2, 1, 3, 5)$ and $(1, 2, 3, 4, 6)$ are not.
A sequence c is a subsequence of a sequence $d$ if $c$ can be obtained from $d$ by deletion of several (possibly, zero or all) elements. For example, $(1, 3, 5)$ is a subsequence of $(1, 2, 3, 4, 5)$ while $(3, 1)$ is not.
The longest common subsequence of the sequences $x$ and $y$ is the longest sequence $z$ which is a subsequence of both $x$ and $y$. For example, the longest common subsequence of the sequences $x = (1, 3, 2, 4, 5)$ and $y = (5, 2, 3, 4, 1)$ is $z = (2, 4)$ since it is a subsequence of both sequences and is the longest among such subsequences. $\text{LCS}(x, y)$ is the length of the longest common subsequence, which is 2ドル$ in the example above.
The first line of the input contains a single integer $t$ (1ドル ≤ t ≤ 10^5$) - the number of test cases. The description of the test cases follows.
The only line of each test case contains 5ドル$ integers $n,ドル $a,ドル $b,ドル $c,ドル $output$ (1ドル ≤ a ≤ b ≤ c ≤ n ≤ 2 ⋅ 10^5,ドル 0ドル ≤ output ≤ 1$).
If $output = 0,ドル just determine if such permutations exist. If $output = 1,ドル you also have to find such a triple of permutations if it exists.
It's guaranteed that the sum of n over all test cases doesn't exceed 2ドル ⋅ 10^5$.
For each test case, in the first line, output "YES", if such permutations $p,ドル $q,ドル $r$ exist, and "NO" otherwise. If $output = 1,ドル and such permutations exist, output three more lines:
In the first line output $n$ integers $p_1 , p_2 , \dots , p_n$ - the elements of the permutation $p$.
In the second line output $n$ integers $q_1 , q_2 , \dots , q_n$ - the elements of the permutation $q$.
In the third line output $n$ integers $r_1 , r_2 , \dots , r_n$ - the elements of the permutation $r$.
If there are multiple triples, output any of them.
You can output each letter in any case (for example, "YES", "Yes", "yes", "yEs", "yEs" will be recognized as a positive answer).
| 번호 | 배점 | 제한 |
|---|---|---|
| 1 | 3 | $a = b = 1,ドル $c = n,ドル $output = 1$ |
| 2 | 8 | $n ≤ 6,ドル $output = 1$ |
| 3 | 10 | $c = n,ドル $output = 1$ |
| 4 | 17 | $a = 1,ドル $output = 1$ |
| 5 | 22 | $output = 0$ |
| 6 | 40 | $output = 1$ |
8 1 1 1 1 1 4 2 3 4 1 6 4 5 5 1 7 1 2 3 1 1 1 1 1 0 4 2 3 4 0 6 4 5 5 0 7 1 2 3 0
YES 1 1 1 NO YES 1 3 5 2 6 4 3 1 5 2 4 6 1 3 5 2 4 6 NO YES NO YES NO
In the first test case, $\text{LCS}((1),(1))$ is 1ドル$.
In the second test case, it can be shown that no such permutations exist.
In the third test case, one of the examples is $p = (1, 3, 5, 2, 6, 4),ドル $q = (3, 1, 5, 2, 4, 6),ドル $r = (1, 3, 5, 2, 4, 6)$. It's easy to see that:
In the fourth test case, it can be shown that no such permutations exist.