#P11720. [清华集训 2014] 虫逢

[清华集训 2014] 虫逢

题目描述

小强和阿米巴是好朋友。

阿米巴告诉小强,变形虫(又叫阿米巴虫)和绝大多数生物一样,也是有 DNA 的。并且,变形虫可以通过分裂的方式进行无性繁殖。

我们把一个变形虫的基因组抽象成一个大小为 LL 的基因集合。每个基因都是一个 44 位长的字符串(字符包括大小写字母、数字、符号 ~!@#%^&()[]`:;"'<>,.?/|=-{}})。现在,有 NN 个变形虫凑到了一起。由于他们是从天南海北过来的,我们可以认为,他们的基因组都是从一个大小为 MM 的“变形虫基因库“中独立的随机的选取 LL 个基因得到的。目前人类并不了解这个基因库里都有什么基因,但是我们知道它的大小是 MM

这时,环境突然发生巨变。这 NN 个变形虫在外界的刺激下同时进行了一次分裂。每个变形虫分裂成了两个。分裂的过程中,原来的变形虫的基因组(基因的集合)被原样的复制成了两份,分别进入两个新的变形虫。两个新变形虫中的一只的基因组中有一半发生了突变,被替换为“变形虫基因库”中随机的其他的基因。如果两个变形虫是由原来的一个变形虫产生的,我们叫它们“同源”的。

给出 2N2N 个变形虫的基因组,请你找出每个变形虫同源的另一只虫是谁。

输入格式

第一行三个整数 NNMMLL

接下来一行 2NL×42NL \times 4个字符,依次表示每个集合中的元素。集合内的元素之间的顺序是无关紧要的。

输出格式

输出 2N2N 行,每行一个整数表示第 ii 个变形虫(从 11 开始标号)同源的另一只变形虫是谁。

2 100 6
H[P,86(^,<n&7X_Sg"LY67m2H$n+5'!VHp5IA.@GM:4-NJsqsiG!H[P,7X_S86(^>aNQ22'B5'!V<FD!F!6xNJsq>!]dHp5I
3
4
1
2

提示

样例解释

输入文件一共有两行。四个基因组分别是:

H[P,86(^,<n&7X_Sg"LY67m2

H$n+5'!VHp5IA.@GM:4-NJsq

siG!H[P,7X_S86(^>aNQ22'B

5'!V<FD!F!6xNJsq>!]dHp5I

明显,1,31,3 是同源的,2,42,4 是同源的。

数据范围

一共有 1010 个测试点。数据均为按照题目中描述的方法随机生成的。对于非同源的两个变形虫,他们的基因组的交的大小均小于 L/2L/2。对于同源的两个变形虫,他们的基因组的交的大小刚好是 L/2L/2

测试点编号 NN MM LL
11 400400 2020
22 900900 3030
33 16001600 4040
44 25002500 5050
55 36003600 6060
66 64006400 8080
77 1000010000 100100
88 1210012100 110110
99 1440014400 120120
1010 1690016900 130130

最大的一个测试数据的大小是 17MB17 \text{MB} 左右(2NL×4=175760002NL \times 4=17576000)。在测评系统上,由于磁盘缓存的存在,使用 scanf 将数据读入需要的时间小于 0.10.1 秒。请不要使用 cin。经测试:

  • 一个实现良好的 O(N2L)O(N^2L) 时间复杂度的算法能拿 30 分,
  • 一个实现良好的 O(N2+N2L2/M)O(N^2 + N^2L^2 / M) 时间复杂度的算法能拿 50 分。