#P9774. [2020年省队模拟]红蓝大作战

    ID: 6400 传统题 1000ms 512MiB 尝试: 3 已通过: 1 难度: 7 上传者: 标签>难度分类提高构造与建模图构造组合数学贡献法奇偶性分析对称性分析CF2200

[2020年省队模拟]红蓝大作战

红蓝大作战(rbfight)

题目描述

有一个 2n2n 行、mm 列的格点棋盘,其中红点和蓝点各有 nmnm 个,保证左上角为红点、右下角为蓝点。

同色格点之间两两连一条边。请为所有这些边定向,使两种颜色的全部边形成的 nm(nm−1)nm(nm-1) 个向量之和为 (0,0)(0,0)。只需输出一种方案;无解则报告无解。

若边从 (x,y)(x,y) 指向 (u,v)(u,v),对应向量为 (u−x,v−y)(u-x,v-y);向量按坐标相加。

输入格式

从标准输入读入。第一行两个整数 n,mn,m;接下来 2n2n 行,每行一个长度为 mm、只含 R 和 B 的字符串,分别表示红点和蓝点。

输出格式

无解时输出 −1-1。

否则输出两行 0101 字符串,第一行描述红点间的边,第二行描述蓝点间的边。

分别将每种颜色的点按从上到下、同一行从左到右的顺序编号为 11 到 nmnm。按 i=1,…,nm−1i=1,\ldots,nm-1,以及每个 ii 对应的 j=i+1,…,nmj=i+1,\ldots,nm 的顺序,依次输出边 (i,j)(i,j) 的方向:i→ji\to j 输出 1,j→ij\to i 输出 0。

每行长度均为 nm(nm−1)/2nm(nm-1)/2。输出量较大,建议使用快速输出。

样例 1 输入

1 2
RR
BB

样例 1 输出

1
0

样例 2 输入

3 1
R
B
R
R
B
B

样例 2 输出

101
101

样例解释

样例 1 的红边从左向右,蓝边从右向左。样例 2 中,每种颜色的三点分别形成有向环。两例的全部向量之和均为 00。

数据范围与约定

所有数据满足 2≤nm≤30002\le nm\le3000。

子任务 分数 额外限制 依赖
1 10 nm≤8nm\le8 无
2 20 nm≤14nm\le14 1
3 nmnm 为奇数 无
4 nm≤100nm\le100 2
5 30 无 3、4

时间限制:1 秒。内存限制:512 MB。