← 返回题目列表

AtCoder · scpc2026_div2_j

J. 排毒

中文机器翻译题面 查看原题

表示言語

/ /

分数: 100 点

问题陈述

N 学生,编号自 1 to N,按数字顺序坐成一圈。每个学生都佩戴一个姓名标签,上面标有 O or X。每个学生都可以看到姓名标签 N-1 学生们, 不包括自己。没有三个或更多坐在一起的学生有带有相同字母的名牌,所有学生都知道这一事实。

进行游戏,直到每个学生都正确猜出自己名牌上的字母。游戏规则继续如下:

  • 每轮中,所有确定名牌上字母的学生同时举手。
  • 一旦所有学生都确认了本轮中哪些学生举手,则下一轮开始。

比赛期间,任何学生不得与他人交换名牌、移除名牌或更改名牌上的字母。

你被给予 T 测试用例。对于每个测试用例,确定每个学生将在哪一轮第一次举手。

约束

  • 1 \le T \le 100\,000
  • 3 \le N \le 100\,000
  • S 是一个长度为的字符串 N 仅包含 O 和 X.
    • 的 i第一个字符 S 是写在姓名标签上的字符 i第学生。
  • 连续坐着的三名学生都没有佩戴写有相同字符的名牌。
  • 总和 N 所有测试用例最多 300\,000.
  • 所有输入数字均为整数。

输入

输入由标准输入按以下格式给出:

T
case_1
case_2
\vdots
case_T

每个测试用例均按以下格式给出:

N
S

输出

输出 N 非负整数,用空格分隔,每个测试用例在一行上。 i第一个整数, r_i,表示 r_i第轮学生 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명의 학생의 명찰을 볼 수 있다. 같은 문자가 적힌 명찰을 달고 있는 학생이 셋 이상 연속해서 앉아 있지 않으며 모든 학생은 이 사실을 알고 있다.

모든 학생이 자신의 명찰에 적힌 문자를 맞힐 때까지 게임을 진행한다. 게임의 규칙은 다음과 같다.

  • 매 라운드마다 자신의 명찰에 적힌 문자를 확신할 수 있는 모든 학생이 동시에 거수한다.
  • 이번 라운드에 어느 학생들이 거수했는지 모든 학생이 확인한 뒤 다음 라운드를 시작한다.

게임을 진행하는 동안 모든 학생은 명찰을 서로 교환하거나 명찰을 떼거나 명찰에 적힌 글자를 바꿀 수 없다.

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가 적힌 명찰을 달고 있다고 확신할 수 있으므로 첫 번째 라운드에 거수한다. 다른 학생들도 같은 근거로 모두 첫 번째 라운드에 거수한다.