問題一覧 > 通常問題

No.3510 RPS Eliminations

レベル : / AI推定難易度 : 2550 / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 1024 MB / 標準ジャッジ問題
タグ : (AC するまで非表示) / 解いたユーザー数 23
作問者 : Nzt3 / テスター : Naru820 Solalyth
お気に入りにしたユーザー ProblemId : 13170 / 自分の提出
問題文最終更新日: 2026-04-17 14:13:22
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
CPCTF 2026: PPC (順位表) の他の問題:

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 R and P, R loses.
      • Between P and S, P loses.
      • Between S and R, S loses.
  • 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)=$R if it exists. If it does not exist, output -1.
  • On line $2$, output the lexicographically $K$-th smallest string $S$ such that $f(S)=$P if it exists. If it does not exist, output -1.
  • On line $3$, output the lexicographically $K$-th smallest string $S$ such that $f(S)=$S if 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 RPRPS gives RPRPS → RPRS → RPS → RS → R.
  • Applying the operations to PPSRS gives PPSRS → PPSR → PSR → PR → P.
  • Applying the operations to PPRPS gives PPRPS → PPRS → PPS → PS → S.

Each of these is number $1$ in lexicographic order, that is, the smallest.

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