← 返回题目列表

AtCoder · joi2026_yo2_c

C. JOI消除器(JOI消除器)

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

配点: 100 点

問題文

J, O, I 组成 它是一个 N 字符串 有 S 。 JOI你是一根绳子 对 S 重复以下操作,直到无法执行进一步操作。 在

  • S 中 J, O, I 以此顺序连续排列。 1 选择一个并选择该部分。 替换为序列 O, I, J 。

可以证明,重复操作总是结束,并且无论操作方法如何,最终字符串的状态都是唯一确定的。

第一个字符串 给定信息 S ,最终字符串 编写一个程序来查找 S 。

制約

  • 3 \leqq N \leqq 500\,000.
  • S 是 J, O, I 组成 它是一个 N 字符串。
  • N 是一个整数。

小課題

  1. (14 点) N \leqq 100.
  2. (27 点) N 是 3 的倍数, 重复 S 是 JOI 在 N / 3 次。
  3. (29 点)一些整数 k (2 \leqq k \leqq N)存在, S 的 1 从第一个字符开始 k 直到第一个字符的所有内容 J ,同时 k + 1 字符之后 它不是 J 。
  4. (30 点)没有额外的限制。 选择

入力

输入格式如下。

N
S

出力

最终字符串 S 在 1 行。 在


入力例 1

6
JOIJOI

出力例 1

OIOIJJ

例如,JOI 可以执行以下操作。

最初,S = JOIJOI 。

  1. 1 从第一个字符开始 3 对第一个字符执行操作。 S = OIJJOI 变为。
  2. 4 从第一个字符开始 6 对第一个字符执行操作。 S = OIJOIJ 变为。
  3. 3 从第一个字符开始 5 对第一个字符执行操作。 S = OIOIJJ 变为。

由于无法执行进一步的操作,OIOIJJ 。

此输入示例是一个小作业。 1,2,4 满足约束。


入力例 2

8
JJJOIOIO

出力例 2

OIOIJJJO

此输入示例是一个小作业。 1,3,4 满足约束。


入力例 3

20
JJOIJOIJOOIJOIIJJOIO

出力例 3

OIOIJJJJOOIOIJIOIJJO

此输入示例是一个小作业。 1,4 满足约束。