시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
2 초 | 512 MB | 1 | 1 | 1 | 100.000% |
The robots battle in rock-paper-scissors takes place in Innopolis. All advanced robots are engaged in full-fledged work, so the simplest bots participate in the battles. Each of them always play the same shape: a rock, or scissors, or a paper.
The robots stand in a line. Then the judge can choose two neighboring robots, and make them play one round of rock-paper-scissors. If one of them beats the other, the loser is eliminated from the game and is removed from the sequence of robots, the sequence of the remaining ones doesn't change. There are two versions of the rules. In the first of them, if the robots played the same shape, the judge can independently choose which one to remove from the game. In the second version, if the robots played the same shape, both robots remain. The robot wins if all other robots are eliminated from the game.
However, the judge has become very bored with the competition, so he wants to find out for each robot whether the judge can choose pairs in each round so that this robot wins. Help him!
You will need to solve several testcases.
The first line contains an integer $t$ ($t \ge 1$) --- the number of tests in the input.
Next, $t$ tests are given, each consisting of an integer and a string.
The integer $d$ denotes the version of the rules that is used in the current robot layout $d \in \{1, 2\}$.
Then the string $s$ follows, it contains $n$ ($1 \le n \le 5 \cdot 10^5$) lowercase English letters 'r
', 'p
' and 's
', describing the list of robots. More precisely, the characters 'r
', 'p
' and 's
' denote robots that play rock, paper, and scissors, respectively.
The total sum of $n$ for $t$ given tests does not exceed $5 \cdot 10^5$.
Output $t$ lines: one for each test.
The line should contain $n$ digits '0
' and '1
', for each $i$ from 1 to $n$ print '1
' if the judge can choose such pairs for each round that the $i$-th robot wins, and '0
' otherwise.
번호 | 배점 | 제한 |
---|---|---|
1 | 7 | $d = 1, \sum n \le 20$ |
2 | 9 | $d = 1, \sum n \le 200$ |
3 | 10 | $d = 1, \sum n \le 5000$ |
4 | 11 | $d = 1, \sum n \le 5 \cdot 10^5$ |
5 | 7 | $\sum n \le 20$ |
6 | 13 | $\sum n \le 200$ |
7 | 10 | $\sum n \le 5000$ |
8 | 33 | $\sum n \le 5 \cdot 10^5$ |
4 1 rpspp 2 pps 1 rpsps 2 rpssprsrr
10111 001 10101 110010001
First test example: "rpspp", $d = 1$. Let's identify the robots with integers from 1 to 5 from left to right.
Second test example: "pps", $d = 2$. Let's identify the robots with integers from 1 to 3 from left to right.