#1903. Chocological
Chocological
Chocological
题目描述
标题: Chocological - Problem - QOJ.ac
#10301. Chocological
有一个 2×n 网格,第 i 行第 j 列的格子记为 (i,j) (1≤i≤2, 1≤j≤n),其中一些格子上存在一个人。
每次操作,你可以从下列选项中选择其一:
- 选择一行 i,然后令该行所有人左对齐,即若原来第 i 行有 x 个人,则将这一行有人的格子修改为所有的 (i,j) (1≤j≤x)。
- 选择一行 i,然后令该行所有人右对齐,即若原来第 i 行有 x 个人,则将这一行有人的格子修改为所有的 (i,n−j+1) (1≤j≤x)。
- 选择一列 j,然后令该行所有人上对齐,即若原来第 j 列有 x 个人,则将这一行有人的格子修改为所有的 (i,j) (1≤i≤x)。
- 选择一列 j,然后令该行所有人下对齐,即若原来第 j 列有 x 个人,则将这一行有人的格子修改为所有的 (2−i+1,j) (1≤i≤x)。
给定初始状态和最终状态(即每个格子上是否有人,保证总人数相同),判断是否可以通过不超过 106 次操作从初始状态转移到最终状态。如果可以,请给出一种方案。
输入格式
第一行:一个整数 n。
第二行:一个长度为 n 的 01 串,其中第 j 个字符为 1 当且仅当初始状态 (1,j) 有人。
第三行:一个长度为 n 的 01 串,其中第 j 个字符为 1 当且仅当初始状态 (2,j) 有人。
第四行:一个长度为 n 的 01 串,其中第 j 个字符为 1 当且仅当最终状态 (1,j) 有人。
第五行:一个长度为 n 的 01 串,其中第 j 个字符为 1 当且仅当最终状态 (2,j) 有人。
输出格式
若无解,输出 NO。
否则,输出 YES,然后:
第一行:一个整数 m,表示操作数量,你需要保证 0≤m≤106。
接下来 m 行:每行两个整数,分别为操作编号(按照题面书写顺序分别为 1,2,3,4)和操作的行/列编号。
样例
输入
6
010100
110001
010001
100011
输出
YES
3
2 1
3 2
4 5
样例
输入
6
000100
000000
001000
000000
输出
NO
子任务
对于全部数据:1≤n≤105。
Subtask 1 (2%):保证无解。
Subtask 2 (13%):n≤10。
Subtask 3 (15%):人数不超过 10。
Subtask 4 (20%):保证有解。
Subtask 5 (10%):人数不超过 n,且初始状态中第 j 个人的位置为 (1,j)。
Subtask 6 (20%):人数不超过 n。
Subtask 7 (20%):无特殊限制。
输入格式
(见题面原文)
输出格式
(见题面原文)
数据范围
(见题面原文)
样例
样例 1
6
010100
110001
010001
100011
YES
3
2 1
3 2
4 5
样例 2
6
000100
000000
001000
000000
NO