/ 
Time Limit: 2 sec / Memory Limit: 1024 MiB
表示言語
/ /Score : 100 points
Problem Statement
N students, numbered from 1 to N, are seated in a circle in numerical order. Each student wears a name tag marked with either O or X. Each student can see the name tags of N-1 students, excluding their own. No three or more students sitting next to each other have name tags with the same letter, and all students are aware of this fact.
The game continues until every student has correctly guessed the letter on their own name tag. The rules of the game are as follows:
- In each round, all students who are certain of the letter on their name tag raise their hands at the same time.
- Once all students have confirmed which students raised their hands in this round, the next round begins.
During the game, no student may exchange name tags with others, remove their name tag, or change the letter on their name tag.
You are given T test cases. For each test case, determine in which round each student will raise their hand for the first time.
Constraints
- 1 \le T \le 100\,000
- 3 \le N \le 100\,000
- S is a string of length N consisting only of
OandX.- The ith character of S is the character written on the name tag of the ith student.
- None of the three students sitting consecutively are wearing name tags with the same characters written on them.
- The sum of N over all test cases is at most 300\,000.
- All input numbers are integers.
Input
The input is given from Standard Input in the following format:
T case_1 case_2 \vdots case_T
Each test case is given in the following format:
N S
Output
Output N non-negative integers, separated by spaces, on a single line for each test case. The ith integer, r_i, indicates the r_ith round in which student i first raises their hand. If there is a student who cannot raise their hand no matter how long the game continues, output -1 instead.
Sample Input 1
4 4 XOXO 3 OOX 3 OXX 6 OXOOXX
Sample Output 1
1 1 1 1 2 2 1 1 2 2 1 1 2 1 1 2
In the first test case, four students are seated in a circle, each wearing a name tag labeled X, O, X, and O, respectively.
In the first round, Student 2 observes that both Student 1 and Student 3 are wearing name tags labeled X. If Student 2 were wearing a badge marked with X, then Students 2, 3, and 4 would all be wearing badges marked with X, which contradicts the rule that three students sitting consecutively cannot all have badges marked with the same character.
Therefore, Student 2 cannot be wearing a name tag marked with an X and can be certain that they are wearing a name tag marked with an O, so they raise their hand in the first round. The other students also raise their hands in the first round based on the same reasoning.
表示言語
/ /점수 : 100 점
문제
1번부터 N번까지 N명의 학생이 번호 순으로 원형으로 둘러앉아 있다. 각 학생은 O 또는 X가 적힌 명찰을 달고 있다. 각 학생은 자신의 명찰을 제외한 N-1명의 학생의 명찰을 볼 수 있다. 같은 문자가 적힌 명찰을 달고 있는 학생이 셋 이상 연속해서 앉아 있지 않으며 모든 학생은 이 사실을 알고 있다.
모든 학생이 자신의 명찰에 적힌 문자를 맞힐 때까지 게임을 진행한다. 게임의 규칙은 다음과 같다.
- 매 라운드마다 자신의 명찰에 적힌 문자를 확신할 수 있는 모든 학생이 동시에 거수한다.
- 이번 라운드에 어느 학생들이 거수했는지 모든 학생이 확인한 뒤 다음 라운드를 시작한다.
게임을 진행하는 동안 모든 학생은 명찰을 서로 교환하거나 명찰을 떼거나 명찰에 적힌 글자를 바꿀 수 없다.
T개의 테스트 케이스가 주어진다. 각 테스트 케이스마다 각 학생이 몇 번째 라운드에 처음으로 거수할지 알아내 보자.
제한
- 1 \le T \le 100\,000
- 3 \le N \le 100\,000
- S는
O와X로만 이루어진 길이 N의 문자열이다.- S의 i번째 문자는 i번 학생의 명찰에 적힌 문자이다.
- 연속해 앉은 어느 세 학생도 같은 문자가 적힌 명찰을 달고 있지 않다.
- 모든 테스트 케이스에 주어지는 N의 합은 300\,000을 넘지 않는다.
- 입력으로 주어지는 수는 모두 정수이다.
입력
입력은 다음 형식으로 표준 입력으로 주어진다.
T case_1 case_2 \vdots case_T
각 테스트 케이스는 다음 형식으로 주어진다.
N S
출력
테스트 케이스마다 N개의 음이 아닌 정수를 공백으로 구분하여 출력한다. i번째 정수 r_i는 i번 학생이 r_i번째 라운드에 처음으로 거수함을 의미한다. 만약 게임을 영원히 진행해도 거수할 수 없는 학생이 있다면 대신 -1을 출력한다.
입력 예 1
4 4 XOXO 3 OOX 3 OXX 6 OXOOXX
출력 예 1
1 1 1 1 2 2 1 1 2 2 1 1 2 1 1 2
첫 번째 테스트 케이스에서는 네 명의 학생이 각각 X, O, X, O가 적힌 명찰을 달고 둘러앉아 있다.
첫 번째 라운드에 2번 학생은 1번 학생과 3번 학생이 모두 X가 적힌 명찰을 달고 있는 걸 확인한다. 이때 2번 학생이 X가 적힌 명찰을 달고 있다면 2번, 3번, 4번 학생이 모두 X가 적힌 명찰을 달고 있으니 연속해 앉은 세 학생이 같은 문자가 적힌 명찰을 달고 있지 않다는 정보와 맞지 않는다.
이로부터 2번 학생은 자신이 X가 적힌 명찰을 달고 있을 수 없고, 따라서 O가 적힌 명찰을 달고 있다고 확신할 수 있으므로 첫 번째 라운드에 거수한다. 다른 학생들도 같은 근거로 모두 첫 번째 라운드에 거수한다.
表示言語
/ /配点 : 100 点
問題文
1番からN番までのN人の生徒が、番号順に円形に座っている。各生徒は、OまたはXと書かれた名札を付けている。各生徒は、自分の名札を除くN-1人の生徒の名札を見ることができる。同じ文字が書かれた名札をつけた生徒が3人以上連続して座っていることはなく、すべての生徒はこの事実を知っている。
すべての生徒が自分の名札に書かれた文字を当てるまでゲームを進める。ゲームのルールは以下の通りである。
- 各ラウンドごとに、自分の名札に書かれた文字に確信が持てる生徒全員が同時に手を上げる。
- 今回のラウンドでどの生徒が挙手したかを全員が確認した後次のラウンドを始める。
ゲームの進行中、すべての生徒は名札を互いに交換したり、名札を外したり、名札に書かれた文字を変更したりすることはできない。
T個のテストケースが与えられる。各テストケースにおいて、各生徒が何番目のラウンドで初めて手を上げるかを求めよ。
制約
- 1 \le T \le 100\,000
- 3 \le N \le 100\,000
- Sは
OとXのみで構成される長さNの文字列である- Sのi番目の文字は、i番目の生徒の名札に書かれた文字である
- どの並んで座っている3人の学生も同じ文字が書かれた名札をつけていない
- すべてのテストケースで与えられるNの合計は300\,000を超えない
- 入力される数値はすべて整数
入力
入力は以下の形式で標準入力から与えられる．
T case_1 case_2 \vdots case_T
各テストケースは以下の形式で与えられる。
N S
出力
N個の非負の整数をスペースで区切り、テストケースごとに1行に出力する。そのうちi番目の整数r_iは、i番目の生徒がr_i番目のラウンドで初めて挙手することを意味する。もしゲームをいつまでも続けても挙手できない生徒がいるなら、代わりに -1 を出力する。
入力例 1
4 4 XOXO 3 OOX 3 OXX 6 OXOOXX
出力例 1
1 1 1 1 2 2 1 1 2 2 1 1 2 1 1 2
最初のテストケースでは、4人の生徒がそれぞれX、O、X、Oと書かれた名札をつけて円になって座っている。
第1ラウンドで、2番の生徒は1番の生徒と3番の生徒がともにXと書かれた名札をつけていることを確認する。このとき、2番の学生がXと書かれた名札をつけているとすると、2番、3番、4番の学生が全員Xと書かれた名札をつけていることになり、隣り合って座っている3人の学生が同じ文字が書かれた名札をつけていないという情報と矛盾する。
したがって、2番の生徒は自分がXと書かれた名札をつけていることはあり得ず、したがってOと書かれた名札をつけていると確信できるため、第1ラウンドで挙手する。他の生徒たちも同様の根拠から、全員第1ラウンドで挙手する。