故事
AtCoder Inc. 最近推出了一个新仓库来存储其在线销售的原创商品。 仓库里有大量箱子,里面装有T恤、钥匙扣、亚克力架等物品,每个箱子都有一个管理编号。
由于箱子是仓促运来的,所以它们被放置在与数量完全无关的地方。 为了以后的库存管理,箱子需要按照管理编号从小到大的顺序从出口取出。
首席执行官高桥决定在仓库安装一条环形传送带,使箱子循环流动,以便以尽可能少的操作将所有箱子取出。
问题陈述
有一个 N\times N 仓库。 让 (0,0) 是左上角单元格的坐标,让 (i,j) 是所在单元格的坐标 i 细胞向下并且 从那里右边的 j 单元格。 细胞 (0,N/2) 包含仓库的出口。
恰好有一个方框,每个数字来自 0 to N^2-1 在仓库里。 初始状态下,cell中放置的盒子的数量 (i,j) is a_{i,j}.
首先,最多安装 N^2 仓库里的环形装置。 此后,每个环形装置称为 传送带.
的 m第一个传送带由一系列单元格表示
\[ (i_{m,0},j_{m,0}), (i_{m,1},j_{m,1}), \ldots, (i_{m,l_m-1},j_{m,l_m-1}) \]
其中 l_m 是传送带的长度。
每条传送带必须满足以下条件。
- l_m\geq 2.
- 对于每个 x=0,\ldots,l_m-1, 0\leq i_{m,x},j_{m,x}<N.
- 细胞 传送带中包含的 (i_{m,0},j_{m,0}),\ldots,(i_{m,l_m-1},j_{m,l_m-1}) 都是不同的。
- 对于每个 x=0,\ldots,l_m-2,细胞 (i_{m,x},j_{m,x}) 和 (i_{m,x+1},j_{m,x+1}) 垂直或水平相邻。
- 细胞 传送带中包含的 (i_{m,l_m-1},j_{m,l_m-1}) 和 (i_{m,0},j_{m,0}) 也垂直或水平相邻。
此外,在所有传送带上, 每个单元格必须包含在最多两条传送带中.
安装传送带后,您最多可以执行 10^5 轮流操作。 在每一回合中,指定传送带编号 m 和一个方向 d\in\{-1,1\},并且该传送带上的所有盒子和空单元同时循环移动一个单元。 即,单元格处的一个框或一个空单元格 (i_{m,x},j_{m,x}) 操作之前移动到单元格之后
\[ (i_{m,(x+d)\bmod l_m},j_{m,(x+d)\bmod l_m}) \]
操作结束后,如果退出单元格中有一个方框 (0,N/2) 且其编号是仓库中剩余箱子中最小的,该箱子通过出口被移除。
If a_{0,N/2}=0 初始状态,方框 0 在执行第一个操作之前被删除。
使用尽可能少的操作,按照管理编号升序移出所有框。
评分
让 T 是输出操作序列的长度,令 B 是成功移出的箱子数量。 然后,您将获得以下分数。
- If B=N^2, 10^6 + \mathrm{round}\left(10^6 \log_2 \frac{10^5}{T}\right)
- If B<N^2, \mathrm{round}\left(10^6\times \frac{B}{N^2}\right)
有 150 测试用例,提交的分数是每个测试用例的总分。 如果您的提交产生非法输出或超出某些测试用例的时间限制,则提交本身将被判断为 WA or TLE ,提交的分数将为零。 比赛期间获得的最高分将决定最终排名,比赛结束后不进行系统测试。 如果超过一名参赛者获得相同分数,则无论提交时间如何,他们都将排名在同一位置。
输入
输入由标准输入按以下格式给出。
N
a_{0,0} \cdots a_{0,N-1}
\vdots
a_{N-1,0} \cdots a_{N-1,N-1}
- 在所有测试用例中, N 固定为 20.
- a_{i,j} 表示单元格中放置的框的编号 (i,j) 处于初始状态。
- a_{i,j} 是满足以下条件的整数 0\leq a_{i,j}\leq N^2-1.
- 数组 a 包含来自的每个整数 0 to N^2-1 恰好一次。
输出
首先,让 M 是要安装的传送带的数量,并按以下格式将其输出到标准输出。
M
l_0 i_{0,0} j_{0,0} \cdots i_{0,l_0-1} j_{0,l_0-1}
\vdots
l_{M-1} i_{M-1,0} j_{M-1,0} \cdots i_{M-1,l_{M-1}-1} j_{M-1,l_{M-1}-1}
然后,让 T 为操作次数,并按以下格式输出操作序列。
T
m_0 d_0
\vdots
m_{T-1} d_{T-1}
在 t第次操作, m_t第一个传送带沿方向循环移动一个单元 d_t.
输出必须满足以下条件。
- 0\leq M\leq N^2
- 长度 每条传送带的 l_m 满足 l_m\geq 2.
- 各坐标 (i_{m,x},j_{m,x}) 满足 0\leq i_{m,x},j_{m,x}<N.
- 每条传送带中包含的单元都是不同的。
- 对于每个传送带,序列中的相邻单元以及最后一个单元和第一个单元在垂直或水平方向上相邻。
- 每个单元必须包含在最多两条传送带中。
- 0\leq T\leq 10^5
- 对于每个操作, 0\leq m_t<M.
- 对于每个操作, d_t is
-1or1.
输入生成
N 固定为 20.
初始放置 盒子的 a 是通过随机排列整数来生成的 0 to N^2-1.
工具(输入生成器和可视化工具)
- 网页版:这比提供动画的本地版本更强大。
- 本地版本: 你需要一个编译环境 Rust 语言.
- Windows 预编译二进制文件:如果你不熟悉Rust语言环境,请使用这个。
请注意,比赛期间禁止分享可视化结果或讨论解决方案/想法。