Parallel Processing (Hard)
这是本题的困难版本,与简单版本的唯一区别是 N 的范围。
题目描述
对于一个未知的幺半群 (M,⊕),希望使用4个CPU并行求出序列的所有前缀运算结果。下面将任务精确规定为一门自定义语言中的整数序列连接程序。请输出满足要求、指令条数最少的程序。
语言规范
程序包含2004个变量:
A[1],A[2],…,A[2000],C1,C2,C3,C4。
每个变量能够保存一个整数序列。初始时,对每个 1≤i≤2000,
A[i]=(i),
即一个仅含整数 i 的序列。
程序执行结束后,必须对所有 1≤i≤N 满足
A[i]=(1,2,…,i)。
其余变量的最终内容不作要求。
一条指令的含义
每条指令由12个整数给出:
c1,a1,b1,c2,a2,b2,c3,a3,b3,c4,a4,b4。
它严格按以下顺序执行:
- C1←concat(A[a1],A[b1])。
- C2←concat(A[a2],A[b2])。
- C3←concat(A[a3],A[b3])。
- C4←concat(A[a4],A[b4])。
- A[c1]←C1。
- A[c2]←C2。
- A[c3]←C3。
- A[c4]←C4。
concat(x,y) 表示将序列 y 接在序列 x 后面,顺序不能颠倒。
因此,四次连接全部读取本条指令开始时的 A 值,然后才依次写回。允许多个 cj 相同,此时编号更大的那一次写回覆盖之前的结果。
输入格式
N
输入仅包含一组数据。
输出格式
第一行输出最小指令条数 L。接下来每条指令占4行:
c_1 a_1 b_1
c_2 a_2 b_2
c_3 a_3 b_3
c_4 a_4 b_4
共输出 4L+1 行,指令按输出顺序执行。每个寄存器编号均须在 1 到 2000 之间。
可以输出任意一个指令条数最少、且最终满足全部前缀要求的程序。
数据范围
- N 为整数。
- 17≤N≤1000。
原题未提供样例。