#P18646. Parallel Processing (Hard)

Parallel Processing (Hard)

Parallel Processing (Hard)

这是本题的困难版本,与简单版本的唯一区别是 NN 的范围。

题目描述

对于一个未知的幺半群 (M,⊕)(M,\oplus),希望使用4个CPU并行求出序列的所有前缀运算结果。下面将任务精确规定为一门自定义语言中的整数序列连接程序。请输出满足要求、指令条数最少的程序。

语言规范

程序包含2004个变量:

A[1],A[2],…,A[2000],C1,C2,C3,C4。A[1],A[2],\ldots,A[2000],C_1,C_2,C_3,C_4。

每个变量能够保存一个整数序列。初始时,对每个 1≤i≤20001\le i\le2000,

A[i]=(i),A[i]=(i),

即一个仅含整数 ii 的序列。

程序执行结束后,必须对所有 1≤i≤N1\le i\le N 满足

A[i]=(1,2,…,i)。A[i]=(1,2,\ldots,i)。

其余变量的最终内容不作要求。

一条指令的含义

每条指令由12个整数给出:

c1,a1,b1,c2,a2,b2,c3,a3,b3,c4,a4,b4。c_1,a_1,b_1,c_2,a_2,b_2,c_3,a_3,b_3,c_4,a_4,b_4。

它严格按以下顺序执行:

  1. C1←concat⁡(A[a1],A[b1])C_1\leftarrow\operatorname{concat}(A[a_1],A[b_1])。
  2. C2←concat⁡(A[a2],A[b2])C_2\leftarrow\operatorname{concat}(A[a_2],A[b_2])。
  3. C3←concat⁡(A[a3],A[b3])C_3\leftarrow\operatorname{concat}(A[a_3],A[b_3])。
  4. C4←concat⁡(A[a4],A[b4])C_4\leftarrow\operatorname{concat}(A[a_4],A[b_4])。
  5. A[c1]←C1A[c_1]\leftarrow C_1。
  6. A[c2]←C2A[c_2]\leftarrow C_2。
  7. A[c3]←C3A[c_3]\leftarrow C_3。
  8. A[c4]←C4A[c_4]\leftarrow C_4。

concat⁡(x,y)\operatorname{concat}(x,y) 表示将序列 yy 接在序列 xx 后面,顺序不能颠倒。

因此,四次连接全部读取本条指令开始时的 AA 值,然后才依次写回。允许多个 cjc_j 相同,此时编号更大的那一次写回覆盖之前的结果。

输入格式

N

输入仅包含一组数据。

输出格式

第一行输出最小指令条数 LL。接下来每条指令占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+14L+1 行,指令按输出顺序执行。每个寄存器编号均须在 11 到 20002000 之间。

可以输出任意一个指令条数最少、且最终满足全部前缀要求的程序。

数据范围

  • NN 为整数。
  • 17≤N≤100017\le N\le1000。

原题未提供样例。