No.3510 RPS Eliminations
Problem Statement
You are given an integer sequence $A=(A_1,\ldots,A_{N-1})$ of length $N−1$.
For a string $S$ consisting only of R,P,S, define $f(S)$ as follows.
Operations
- Perform $N-1$ operations in the order $i=1,2,\ldots,N-1$.
- If $S_{A_i} = S_{A_{i}+1}$, abort the operations.
- Otherwise, the winner between $S_{A_i}$ and $S_{A_i+1}$ is decided by rock-paper-scissors. Remove the loser.
- Between
RandP,Rloses. - Between
PandS,Ploses. - Between
SandR,Sloses.
- Between
- Let $f(S)$ be the string after performing the $N-1$ operations.
The constraints on $A$ guarantee that the $N-1$ operations can be performed if the string $S$ is chosen appropriately.
For each of $f(S)=$R,P,S, find the lexicographically $K$-th smallest string $S$ satisfying it.
If no such string exists, report that.
You are given $T$ test cases; solve the above problem for each test case.
Constraints
- $1 \le T \le 10^5$
- $2 \le N \le 2 \times 10^5$
- $1 \le A_i \le N- i\ (1 \le i \le N-1)$
- $1 \le K \le 10^{18}$
- In $1$ file, the sum of $N$ over all test cases is at most $2 \times 10^5$.
- All input values are integers.
Input
The input is given from standard input in the following format. Here, $\text{case}_i$ denotes the $i$-th test case.
$T$
$\text{case}_1$
$\text{case}_2$
$\vdots$
$\text{case}_T$
Each test case consists of $2$ lines and is given in the following format.
$N$ $K$
$A_1 A_2 \dots A_{N-1}$
Output
For each test case, output $3$ lines as follows.
- On line $1$, output the lexicographically $K$-th smallest string $S$ such that $f(S)=$
Rif it exists. If it does not exist, output-1. - On line $2$, output the lexicographically $K$-th smallest string $S$ such that $f(S)=$
Pif it exists. If it does not exist, output-1. - On line $3$, output the lexicographically $K$-th smallest string $S$ such that $f(S)=$
Sif it exists. If it does not exist, output-1.
Sample
Sample 1
Input
3 5 1 4 2 2 1 5 3 4 2 2 1 7 10000 6 2 2 1 1 1
Output
RPRPS PPSRS PPRPS RPSPR PRSPS PPSPR -1 -1 -1
In test case $1$, the operations proceed as follows.
- Applying the operations to
RPRPSgivesRPRPS→RPRS→RPS→RS→R. - Applying the operations to
PPSRSgivesPPSRS→PPSR→PSR→PR→P. - Applying the operations to
PPRPSgivesPPRPS→PPRS→PPS→PS→S.
Each of these is number $1$ in lexicographic order, that is, the smallest.
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。
Solalyth