[R62C]机器人巡逻 - 代码源竞赛平台

时空限制

1S/512M

题目描述

在一个一维数轴上有 $n$ 个格子，从左到右编号为 $1$ 到 $n$。每个格子初始时都没有印章。

有一个机器人，初始时位于第 $P$ 个格子，面朝右侧（即朝向编号增大的方向），且初始工作状态为 1。

现在依次给定 $Q$ 个操作，操作分为以下三种类型：

• 1 x：沿着机器人当前的面朝方向，尝试执行 $x$ 次以下步骤：

  1. 机器人尝试向前迈出一步。如果下一步超出了格子范围（即当前处于第 $1$ 个格子且面朝左，或处于第 $n$ 个格子且面朝右），则机器人会立即终止整个操作（即使 $x$ 次步骤还未执行完毕）。
  2. 否则，机器人移动到该相邻格子中。
  3. 机器人根据当前的工作状态来决定是否改变新到达格子的印章状态：
     • 若机器人处于工作状态 $1$：改变新到达格子的印章状态（若该格子已有印章，则将其删除；若该格子没有印章，则在其中加上印章）。
     • 若机器人处于工作状态 $2$：不改变任何格子的状态，仅进行移动。

• 2：切换机器人的面朝方向（如果当前面朝右，则切换为面朝左；如果当前面朝左，则切换为面朝右）。

• 3：切换机器人的工作状态（如果当前为状态 1，则切换为状态 2；如果当前为状态 2，则切换为状态 1）。

请在所有操作执行完毕后，输出每个格子的印章状态。

格式

输入格式

第一行包含三个正整数 $n, Q, P$，分别表示格子的数量、操作的数量以及机器人的初始位置。

接下来 $Q$ 行，每行描述一个操作：

• 操作 1 的格式为：1 x，其中 $x$ 为一个正整数。
• 操作 2 的格式为：2。
• 操作 3 的格式为：3。

输出格式

输出一行一个长度为 $n$ 的由 0 和 1 组成的字符串。 其中第 $i$ 个字符表示第 $i$ 个格子的最终状态：若第 $i$ 个格子在所有操作结束时有印章，则为 1；否则为 0。

样例

样例输入 #1

5 6 2
1 2
3
2
1 2
3
1 2

样例输出 #1

10110

数据规模

注意：你只有通过了子任务的所有测试点，才能获得对应子任务的分数。

子任务编号	分数	$n\le$	$Q\le$
$1$	$40$	$2000$
$2$	$60$	$2\times 10^5$

对于 $100\%$ 的数据，$1 \le n, Q \le 2 \times 10^5$，$1 \le P \le n$，$1 \le x \le n$。