QOJ.ac

QOJ

Time Limit: 2 s Memory Limit: 1024 MB

# 8744. 机器人

统计

题目背景

注意本题的指令含义与初赛的略有不同。

题目描述

有 $n$ 个机器人围成一圈,编号按照逆时针顺序分别为 $0\sim n-1$。

每个机器人有两只手。编号为 $i$ 的机器人初始「左手」指向编号 $l_i$ 的机器人,「右手」指向编号 $r_i$ 的机器人。

所有的机器人内部都写有一条「指令」,「指令」有以下这些形式:

指令

下面介绍这些「指令」的格式以及它们被「执行」时的效果。文中的“自己”一词均指拥有这条「指令」的机器人。

  • SLACKOFF「摸鱼」,即什么也不做。
  • MOVE h z:将第 $h$ 只手向逆时针方向「移动」$z$ 个机器人的位置。当 $h=0$ 时表示「左手」,当 $h=1$ 时表示「右手」,下同。
  • SWAP「交换」双手指向的机器人的「指令」。
  • TRIGGER <COMMANDNAME>: <COMMAND>:其中 <COMMANDNAME>SLACKOFFMOVESWAPTRIGGERTOGGLETRIGGERREPLACE 之一;<COMMAND> 表示一条完整的非 TRIGGER 「指令」。TRIGGER 指令本身不会被「执行」,但是,当一个其他机器人「执行」完一条「指令」之后,且「右手」指向自己的时候,自己满足如下条件的 TRIGGER 指令(如果有)就会被「触发」——「执行」一次对应的 <COMMAND>
    • <COMMANDNAME> 不为 TRIGGER 时,刚刚「执行」完毕的「指令」为 <COMMANDNAME> 指令;
    • <COMMANDNAME>TRIGGER 时,刚刚「执行」完毕的「指令」是一条 TRIGGER 指令被「触发」时,「执行」的 <COMMAND> 部分。
  • TOGGLETRIGGERREPLACE h <COMMANDNAME> <NEWCOMMAND>:如果第 $h$ 只手指向的机器人的「指令」是 TRIGGER 指令,则将其「切换」为该「指令」的 <COMMAND> 部分,即删去前面的 TRIGGER 及条件部分;如果这条「指令」不是 TRIGGER 指令,假设是 <COMMAND>,则将其「切换」为 TRIGGER <COMMANDNAME>: <COMMAND>。其中 <COMMANDNAME>SLACKOFFMOVESWAPTRIGGERTOGGLETRIGGERREPLACE 之一。然后将自己的「指令」(注意这可能不仅仅包含正在「执行」的那部分「指令」)修改为 <NEWCOMMAND>。其中,<NEWCOMMAND> 是一条完整的「指令」。

机器人「执行」各「指令」时的输出格式如下:

  • 「摸鱼」时输出 Robot <id> slacks off.。其中 <id> 为一个整数,表示「执行」当前「指令」的机器人编号,下同。
  • 「移动」时输出 Robot <id> moves its <side> hand towards Robot <id2>.。其中 <side>leftright,表示移动了哪只手(left 表示「左手」,right 表示「右手」);<id2> 为一个整数,表示移动之后这只手指向的机器人的编号。
  • 「交换」时输出 Robot <id> swaps the commands of Robot <id2> and Robot <id3>.。其中 <id2><id3> 为整数,表示被「交换」「指令」的机器人编号,这两个数可以按任意顺序输出。
  • 「切换」时输出 Robot <id> toggles the trigger property of the command of Robot <id2>
  • TRIGGER 指令不会被「执行」,但当它们被「触发」时,会按照上面的格式输出对应的「指令」被「执行」的信息。

你按照一定顺序选择了一些机器人(可能重复选择)并「执行」了对应机器人的「指令」,得到了「执行」的完整输出,也就是说,在「执行」完输出中最后一条「指令」之后,没有其他「指令」被「触发」。但是,你忘记了你选择机器人的顺序,也忘了每个机器人开始时有什么「指令」。你只记得机器人的总数以及开始时每个机器人的手指向什么位置。

你想通过已知的所有信息还原出最初所有机器人的「指令」都是什么。

输入格式

从标准输入读入数据。

第一行两个正整数 $n,k$,其中 $k$ 表示输出的总行数。

接下来 $n$ 行,每行两个整数 $l_i,r_i$,按编号从小到大的顺序输入。

接下来 $k$ 行,每行一条「执行」「指令」的输出信息。

为了减轻处理输入的负担,输出信息被简化如下(没有特殊声明的参数信息含义同上):

  • 「摸鱼」时输出 SLACKOFF <id>
  • 「移动」时输出 MOVE <id> <side> <id2>。其中 <side>01,表示移动了哪只手(0 表示「左手」,1 表示「右手」)。
  • 「交换」时输出 SWAP <id> <id2> <id3>
  • 「切换」时输出 TOGGLETRIGGERREPLACE <id> <id2>
  • TRIGGER 指令不会被「执行」,但当它们被「触发」时,会按照上面的格式输出对应的「指令」被「执行」的信息。

输入保证存在一组初始的「指令」,使得存在一种选择机器人的方式,能够得到对应的输出。

保证 $1\le n,k \le 500000$。

保证 $0\le l_i,r_i

输出格式

输出到标准输出。

输出 $n$ 行,按编号从小到大输出机器人最初的「指令」,每条一行。

你需要保证「指令」格式正确,且 $0\le z < n$。

你需要保证你的输出文件不能过大。若你的输出文件大小不超过 $100\texttt{MB}$,则一定能保证 Special Judge 能够正确返回结果。

此外任何能够得到输入中 $k$ 行输出的答案均算作正确。

样例

输入

4 7
1 3
2 0
3 0
2 1
SWAP 1 0 2
SWAP 0 1 3
SWAP 1 2 0
MOVE 0 0 2
SWAP 1 0 2
SWAP 0 2 3
MOVE 3 0 3

输出

MOVE 0 1
SWAP
TRIGGER SWAP: SWAP
SWAP

解释

选择机器人的顺序为 $1,1,0,1,3$,其中第二、六条被「执行」的「指令」是「触发」TRIGGER 指令之后被「执行」的。

注意 TRIGGER 指令「触发」的时机是在「执行」上一条「指令」之后,所以第一次「交换」之后由于 $1$ 号机器人的「右手」指向了写有 TRIGGER SWAP: SWAP 的 $0$ 号机器人,所以这条 TRIGGER 指令能被「触发」。

样例

输入

4 7
1 2
2 3
3 1
0 2
TOGGLETRIGGERREPLACE 0 1
SLACKOFF 3
MOVE 0 1 3
SWAP 1 2 3
TOGGLETRIGGERREPLACE 3 2
SLACKOFF 2
SLACKOFF 3

输出

TOGGLETRIGGERREPLACE 0 MOVE MOVE 1 1
TRIGGER SLACKOFF: SWAP
TRIGGER SWAP: TOGGLETRIGGERREPLACE 1 TOGGLETRIGGERREPLACE SLACKOFF
SLACKOFF

解释

选择机器人的顺序为 $0,3,0,1,3$,其中第五、六条被「执行」的「指令」是「触发」TRIGGER 指令之后被「执行」的。

第一次「执行」会使 $1$ 号机器人的「指令」变为 SWAP,$0$ 号机器人的「指令」变为 MOVE 1 1

第五次「执行」会使 $2$ 号机器人的「指令」由 SLACKOFF 变为

TRIGGER TOGGLETRIGGERREPLACE: SLACKOFF

,$3$ 号机器人的「指令」由

TRIGGER SWAP: TOGGLETRIGGERREPLACE 1 TOGGLETRIGGERREPLACE SLACKOFF

会变为 SLACKOFF 而不是 TRIGGER SWAP: SLACKOFF

样例

输入

4 4
2 1
1 2
0 3
1 3
SLACKOFF 0
SLACKOFF 1
SLACKOFF 2
SLACKOFF 3

输出

SLACKOFF
TRIGGER SLACKOFF: SLACKOFF
TRIGGER SLACKOFF: SLACKOFF
TRIGGER TRIGGER: SLACKOFF

解释

选择机器人的顺序为 $0$,其中第二、三、四条被「执行」的「指令」是「触发」TRIGGER 指令之后被「执行」的。

注意 $3$ 号机器人「执行」完「指令」后不会接着「触发」自己的 TRIGGER 「指令」,即使它的「右手」指向了自己。

另外,选择一个写有 TRIGGER 指令的机器人不会产生任何输出,所以这么做没有意义。

样例4

见题目目录下的 4.in。该样例不提供样例输出。

样例5

见题目目录下的 5.in。该样例不提供样例输出。

提示

我们会下发一个可执行文件 checker 来帮助你检查你的输出是否正确。使用方式为在该文件所在目录下使用如下指令:

./checker <输入文件路径> <你的输出文件路径>

若你的输出正确,程序会输出 Accepted.;否则会提示「执行」结果与输入文件最早一次不匹配的地方。

注意,若你使用的输入文件不是样例输入,该程序不会检查是否存在一组初始的「指令」,使得存在一种选择机器人的方式,能够得到对应的「执行」结果。