评测环境与性能 / Environment and measurements¶
环境与口径¶
测量平台为 Intel Core Ultra 9 275HX、Windows 11（10.0.26200）、GCC 16.2.0、Python 3.12.14。C++ 编译选项为 -std=c++17 -O2 -DNDEBUG -Wall -Wextra -Wpedantic .
每份输入先运行一次生成答案并读取进程峰值工作集，再独立计时五次，取中位数；树形压力构造的确认与校准使用七次，原始记录注明次数。比较两份程序时交替运行顺序。整题取所有用例中最大的中位数，乘以 2，再按 0.5 秒向上取整。计时包含进程启动、读入和输出，不包含数据生成与校验；峰值工作集包括进程运行开销。时间与内存列分别取最大值，可能来自不同用例。
Measurements use the platform and compiler flags above. Each input has one output-generation and peak-memory run followed by five timed runs; targeted tree confirmations and calibration use seven, as recorded in the raw data. Comparisons alternate program order. The limit is twice the largest per-case median, rounded up to a multiple of 0.5 seconds. Timings include startup and I/O; peak working set includes process overhead. Time and memory maxima may come from different inputs. Recalibrate on the target judge.
标准程序 / Reference programs¶
原始记录保存每次耗时、输入及源码哈希。表中记录编号用于定位测量数据；每道题的标准程序由题解说明。
Raw records contain individual timings and input/source hashes. Record identifiers locate measurements; the editorial describes each reference algorithm.
| 题目 / Problem | 最慢中位数 / Median (s) | 峰值 / Peak (MiB) | 时限 / Limit (s) | 原始记录 / Record |
|---|---|---|---|---|
| Grox的序列二 | 0.018029 | 5.49 | 0.5 | R13 |
| Grox的序列四 | 0.476734 | 125.83 | 1.0 | R14 |
| Grox的序列五A | 0.035063 | 5.31 | 0.5 | R14 |
| Grox的序列五B | 0.124843 | 9.89 | 0.5 | R14 补充方案 |
| 犀牛坦克 | 0.016224 | 4.79 | 0.5 | R7 |
| 土罐的序列 | 0.500597 | 13.07 | 1.5 | R12 |
| 催化序列 | 2.320083 | 6.48 | 5.0 | R13 |
| 贸易 | 0.856212 | 30.99 | 2.0 | P1 |
| 契约召唤 | 0.343641 | 50.36 | 1.0 | R12 |
| 饼干交换大会 | 0.142132 | 28.67 | 0.5 | R3 |
| 晶块链表 | 0.160916 | 14.20 | 0.5 | P1 |
| 格兰之森 | 0.339292 | 111.99 | 1.0 | P1 |
| 抽奖插件 | 4.051822 | 190.66 | 8.5 | R9 |
| 纳米电脑主机 | 0.088271 | 23.66 | 0.5 | R6 |
| 心灵突击队 | 0.045189 | 35.29 | 0.5 | R4 |
| 插火把 | 0.286966 | 78.30 | 1.0 | R7 |
| 真空内爆弹 | 0.422816 | 19.99 | 1.0 | P1 |
| 菁英战斗兵 | 0.374307 | 29.29 | 1.0 | R4 |
| 基因突变 | 0.064357 | 4.87 | 0.5 | R7 |
| 种西瓜 3 | 0.083996 | 4.95 | 0.5 | R10 |
| 剪羊毛 | 0.025347 | 9.17 | 0.5 | R9 |
| 升级工具箱 | 0.041700 | 4.82 | 0.5 | R6 |
| 游耕者（昼） | 0.383566 | 64.10 | 1.0 | R8 |
| 游耕者（夜） | 0.572492 | 41.36 | 1.5 | R8 |
| 麦田选址 | 0.017389 | 4.78 | 0.5 | R7 |
| 自动接线器 | 0.142000 | 11.54 | 0.5 | R11 |
| 修桥笑传之坚决不用第一版方案 | 0.144419 | 35.62 | 0.5 | R1 |
| 神经突击车 | 0.019698 | 5.88 | 0.5 | R6 |
| 超时空军团 | 0.045311 | 5.51 | 0.5 | R5 |
| 种西瓜 2 | 0.467795 | 4.78 | 1.0 | R10 |
| 种西瓜 | 0.052336 | 4.82 | 0.5 | R9 |
| 红石计算机 | 0.193540 | 7.82 | 0.5 | R7 |
| Spode经学院 | 0.155689 | 9.38 | 0.5 | R13 |
| 恐怖机器人 | 0.059335 | 4.88 | 0.5 | R5 |
| 旅游安排 | 2.813958 | 6.37 | 6.0 | R11 |
| 两色徽章 | 0.160791 | 14.20 | 0.5 | R2 |
| Grox的序列六 | 0.045171 | 5.84 | 0.5 | R14 |
| Grox的序列七 | 0.259446 | 7.32 | 1.0 | R14 |
| 病毒狙击手 | 0.300086 | 16.89 | 1.0 | R5 |
| 农务署 | 0.029483 | 5.05 | 0.5 | R9 |
| 装备增幅 | 0.366096 | 4.82 | 1.0 | R13 |
| 数据恢复 | 0.072393 | 9.41 | 0.5 | R12 |
| Grox的序列三 | 0.276906 | 7.49 | 1.0 | R13 |
| 红石钟 | 1.268285 | 4.25 | 3.0 | R7 |
| 世纪轰炸机 | 0.017304 | 4.26 | 0.5 | R7 |
| 力场护盾 | 0.370392 | 115.35 | 1.0 | R6 |
| 坐地铁 | 0.051249 | 19.32 | 0.5 | R11 |
| 乘客需要多运动 | 0.014868 | 4.80 | 0.5 | R2 |
| 短板翻盘 | 0.151246 | 46.63 | 0.5 | R3 |
| 地精排序 | 0.130197 | 12.79 | 0.5 | R14 |
| 合成大星星 | 0.133010 | 4.85 | 0.5 | R1 |
| 吃糖果 | 0.393056 | 73.69 | 1.0 | R1 |
| 克隆缸 | 0.099328 | 6.39 | 0.5 | R6 |
| 再来一小段 | 0.161011 | 4.79 | 0.5 | R3 |
| 魔法面包 | 0.455435 | 14.06 | 1.0 | R11 |
| 告示牌识别 | 0.101781 | 12.46 | 0.5 | R9 |
| 动态目录树 | 0.732673 | 33.77 | 1.5 | R12 |
| 庆典计划 | 1.746265 | 57.93 | 3.5 | 树形压力数据 |
| 粉碎者 | 1.101980 | 63.93 | 2.5 | 树形压力数据 |
| 哈根农场 | 0.024228 | 4.83 | 0.5 | R13 |
| 护林员 | 0.246618 | 50.56 | 0.5 | P1 |
| 光棱坦克 | 0.146984 | 4.94 | 0.5 | R4 |
| 心灵支配树 | 0.848854 | 25.93 | 2.0 | P1 |
| 香料航线 | 0.061548 | 14.16 | 0.5 | P1 |
| 砍树 | 0.238098 | 36.56 | 0.5 | R9 |
| 简单统计 | 0.044081 | 6.46 | 0.5 | R15 |
| 简单合并 | 0.176663 | 9.00 | 0.5 | R15 |
| 区间最值 | 0.080116 | 9.06 | 0.5 | R15 |
| 区间中位数 | 0.074143 | 9.11 | 0.5 | R15 |
| 异星工厂：科技树 | 0.447671 | 43.34 | 1.0 | R15 |
| 二叉树遍历 | 0.200720 | 24.30 | 0.5 | R15 |
| 简单分析 | 0.108609 | 9.95 | 0.5 | R15 follow-up |
| 随机分析：期望 | 0.030652 | 5.31 | 0.5 | R15 follow-up |
| 随机分析：概率 | 0.035418 | 5.99 | 0.5 | R15 follow-up |
| 纸老虎序列 | 0.070396 | 9.04 | 0.5 | R16 |
| 异星工厂：简单火车 | 0.710041 | 35.69 | 1.5 | R16 |
| 积木塔 | 0.029726 | 5.31 | 0.5 | R16 |
| 异星工厂：测试电路板 | 0.027496 | 5.32 | 0.5 | R16 |
| 异星工厂：分拣流水线 | 0.029646 | 5.61 | 0.5 | R17 |
| 异星工厂：机器人指令平台 | 0.130818 | 6.71 | 0.5 | R17 |
| 猜公因子 | 0.156365 | 13.90 | 0.5 | R17 |
| 星际订单：加速度 | 0.026736 | 5.33 | 0.5 | R18 |
| 星际订单：矩形相交 | 0.028026 | 5.32 | 0.5 | R18 |
| 星际订单：交集分类 | 0.028374 | 5.32 | 0.5 | R18 |
| 异星工厂：搅拌机 | 0.050415 | 5.32 | 0.5 | R18 |
| 疯狂的串串 | 0.033788 | 5.33 | 0.5 | R18 |
| 优选猫咪 | 0.027754 | 5.32 | 0.5 | R18 |
| 字符 X | 0.027682 | 5.30 | 0.5 | R19 |
| 递归训练：最大值 | 0.028197 | 5.31 | 0.5 | R19 |
| 无限二叉树上的距离 | 0.067031 | 5.32 | 0.5 | R19 |
| 变量列表 | 0.227879 | 35.70 | 0.5 | R19 |
| 滴嘟hia的能指循环 | 0.035709 | 6.88 | 0.5 | R19 |
| 异星工厂：信号网络 | 0.231701 | 5.31 | 0.5 | R19 |
两种实现的比较 / Comparing implementations¶
以下为同环境、同一套输入上的测量。算法名称与署名见各题题解；“通过”只指这些已测输入与参考时限。更多参数范围的复杂度、适用条件与理论分析也见题解。
These programs were measured on the same inputs and platform. “Pass” refers to the measured inputs under the reference limit. Editorials describe attribution, complexity and applicable parameter ranges.
| 题目 | std.cpp 算法 | alternative.cpp 算法 | std / alternative 最慢中位数 (s) | std / alternative 峰值 (MiB) | alternative 状态 |
|---|---|---|---|---|---|
| 贸易 | 在线伸展树 | 离线离散化线段树 | 0.856212 / 0.614171 | 30.99 / 115.27 | 通过 / Pass |
| 晶块链表 | 同类标记线段树 | 有序区间表 | 0.160916 / 0.214764 | 14.20 / 29.62 | 通过 / Pass |
| 格兰之森 | 每条重链独立分块 | 全局分块 | 0.339292 / 1.973137 | 111.99 / 56.90 | 平衡树超时 / TLE on balanced tree |
| 真空内爆弹 | 交换、符号、旋转与平移专用标记 | 仿射矩阵 | 0.422816 / 0.371126 | 19.99 / 23.05 | 通过 / Pass |
| 庆典计划 | 重心分治与单调队列 | 重心分治与线段树 | 1.746265 / 1.393669 | 57.93 / 55.32 | 通过 / Pass |
| 粉碎者 | 限制度数、边分治与单调队列 | 点分治与线段树 | 1.101980 / 0.680879 | 63.93 / 38.27 | 通过 / Pass |
| 护林员 | 最长链收益与计数桶 | 比较排序 | 0.246618 / 0.254445 | 50.56 / 50.54 | 通过 / Pass |
| 心灵支配树 | 轻子树清空、重子树保留与根路径并集 | 小并大集合与 DFS 序环距离和 | 0.848854 / 0.764023 | 25.93 / 32.49 | 通过 / Pass |
| 香料航线 | 至多两个高价点的路径分类 | 三状态树 DP | 0.061548 / 0.067255 | 14.16 / 15.34 | 通过 / Pass |
双程序基础记录见 benchmark-P1.json；庆典计划与粉碎者的表中数值同时覆盖树形压力数据中正式范围内的重复测量。格兰之森的同一平衡树用例中，逐链分块约为 0.230004 秒，全局分块五次为 1.957402–2.029864 秒，中位数为 1.973137 秒；后者超过 1.0 秒时限。这一结果针对随附实现。
Baseline paired measurements are in benchmark-P1.json. The Festival Plan and Grinder rows also include repeated tree stress measurements within their formal limits. On Gran Forest’s same balanced-tree input, per-chain blocks take about 0.230004 seconds. Global blocks take 1.957402–2.029864 seconds over five runs, with median 1.973137 seconds, exceeding the 1.0-second limit. This result concerns the supplied implementation.
规模与操作次数 / Scale and operation counts¶
另有护林员四百万节点、庆典计划两百万节点、粉碎者一百万节点的性能实验。这些规模超出题面正式上限，仅用于分析增长趋势，详见扩大规模的测量。随机树、梳形树、长臂树和长链窗口均未形成可用上述时限余量可靠排除另一份程序的差距。理论上多一个对数因子，并不保证在这些输入规模上就有明显耗时差。
Additional experiments use four million vertices for Forest Ranger, two million for Festival Plan and one million for Grinder. These exceed the published limits and serve only to examine scaling; see the scale measurements. Random trees, combs, spiders and chain windows do not provide a reliable exclusion gap with the stated timing margin. An extra logarithmic factor need not produce a large runtime gap at these sizes.
实际排序比较次数、分治块大小与线段树查询循环次数见操作统计。它们衡量执行的工作量，不能代替各阶段计时或缓存测量。四题题解分别解释了收益数量与分布、局部深度、虚点扩树和分块粒度对耗时的影响。
The operation counts measure sorting comparisons, decomposition sizes and segment-tree query iterations. They do not measure phase durations or cache behavior. The editorials explain gain distributions, local depths, dummy-vertex expansion and block granularity.
定向树形压力数据 / Targeted tree stress inputs¶
树形构造与性能给出 81 份候选输入的构造范围、重复计时、选主元构造及复现方法。完整记录保留所有轮次的输入、源码与程序哈希。
护林员的选主元构造在百万节点时让排序约慢 30%，四百万节点时约慢 48%；这是可测差异，仍不足以在两倍标程余量下排除排序实现。庆典计划的梳形树在百万节点时约慢 24%；粉碎者的线段树方案在已测输入上仍更快。规模实验均不改变题面范围。
庆典计划与粉碎者的正式计划包含随机重编号长链。与基础记录及正式范围内的已测构造合并后，标程最慢中位数分别为 1.746265 和 1.101980 秒，按相同公式得到 3.5 和 2.5 秒参考时限。数据构造署名：Codex（GPT-6）。
Tree constructions and performance describes the 81 screening inputs, repeated measurements and reproduction. The full record preserves per-stage input, source and binary hashes. Pivot-targeted sorting is about 30% slower at one million vertices and 48% slower at four million; Festival Plan's million-vertex comb gives about 24%. None provides an exclusion gap with twice the reference time, while Grinder's segment-tree method remains faster. Scaling experiments do not change published size limits.
The formal Festival Plan and Grinder plans include randomly relabeled chains. Taking the largest reference median across the baseline and measured inputs within the formal limits gives 1.746265 and 1.101980 seconds, hence limits of 3.5 and 2.5 seconds under the same formula. Stress input attribution: Codex (GPT-6).
Grox 序列四的时间与空间 / Time and space for Grox's Sequence IV¶
分阶段 FWT 与逐块 FWT 在10份正式输入上的输出完全一致；五轮交替计时见 R14。分阶段方案最慢中位时间为 0.466883 秒，逐块方案为 0.892257 秒；参考峰值分别为 125.83 与 17.16 MiB。两者都通过已测输入的 1.0 秒时限。逐块方案有明确空间优势，作为并列方案保留。
The phased and per-square FWTs agree on all 10 formal inputs. Five alternating runs are recorded in R14. Their largest comparison medians are 0.466883 and 0.892257 seconds; reference peak working sets are 125.83 and 17.16 MiB respectively. Both meet the 1.0-second limit on measured inputs. The per-square option is retained for its clear space advantage.
R14 补充方案 / Supplementary options¶
各补充程序均与标程在 10 份相同正式输入上输出一致。表中为五轮交替计时的最慢用例中位耗时及独立测得的峰值工作集，完整轮次与哈希见测量记录。序列五 B 的标程使用截短到所需前缀的 Stirling 卷积。
Each supplementary program agrees with the reference on the same 10 formal inputs. The table gives the largest per-input median over five alternating runs and separately measured peak working sets. Full runs and hashes are in the measurement record. The V B reference uses Stirling convolution truncated to the required prefix.
| 题目 / Problem | 补充方案 / Option | 标程 / 补充 秒 | 标程 / 补充 MiB | 当前时限 / Current limit |
|---|---|---|---|---|
| Grox的序列四 | 余数值张量变换 | 0.499386 / 0.584175 | 125.83 / 41.74 | 已测输入通过 / Measured inputs pass |
| Grox的序列五A | 十进制模幂与连续乘二 | 0.036134 / 0.035908 | 5.30 / 5.32 | 已测输入通过 / Measured inputs pass |
| Grox的序列五B | 指数生成函数与形式级数 | 0.124843 / 0.637622 | 9.89 / 14.93 | 超时，备用 / TLE, backup |
| Grox的序列六 | Newton 二项式基底 | 0.045359 / 0.081370 | 5.84 / 5.33 | 已测输入通过 / Measured inputs pass |
| Grox的序列七 | 乘积树与多点求值 | 0.277414 / 0.843589 | 7.31 / 7.62 | 已测输入通过 / Measured inputs pass |
| 地精排序 | 离散化与树状数组 | 0.142160 / 0.148444 | 12.79 / 18.53 | 已测输入通过 / Measured inputs pass |
序列四的余数值方案保持时间阶并降低空间阶；序列六的 Newton 方案降低预处理与空间阶，但不同操作组合下并非总是更快。序列七乘积树在渐进意义上降低增长阶，在当前规模的实测仍慢于逐对相乘。序列五 B 的形式级数程序在 6 份已测输入上超出 0.5 秒时限，只作为正确的备用算法展示。
The residue-valued IV option keeps the time bound and reduces space. The Newton VI option reduces preprocessing and space bounds, but is not faster for every operation mix. The VII product tree reduces asymptotic growth but is slower than pairwise multiplication at measured sizes. The V B formal-series implementation exceeds the 0.5-second limit on 6 measured inputs and is presented only as a correct backup algorithm.
R15 补充方案 / Additional algorithms¶
六题各两份程序在相同十份输入上交替计时五轮，输出一致。差分筛的整除分块并列方案、双堆的低空间滑动窗口方案，以及其余三种不同遍历或数据结构方案均保留。逐题说明见对应题解。
Two programs per problem were alternated for five timing rounds on the same ten inputs, with identical outputs. The editorials preserve the quotient-block parallel option, lower-space sliding windows, and the other traversal or data-structure alternatives.
| 题目 / Problem | 标程中位数 / Reference (s) | 补充中位数 / Alternative (s) | 标程峰值 / Reference (MiB) | 补充峰值 / Alternative (MiB) | 状态 / Status |
|---|---|---|---|---|---|
| 简单统计 | 0.044081 | 0.322212 | 6.46 | 6.01 | 已测输入通过 / Pass on measured inputs |
| 简单合并 | 0.176663 | 0.159656 | 9.00 | 9.01 | 已测输入通过 / Pass on measured inputs |
| 区间最值 | 0.080116 | 0.206423 | 9.06 | 5.38 | 已测输入通过 / Pass on measured inputs |
| 区间中位数 | 0.074143 | 0.206148 | 9.11 | 5.38 | 已测输入通过 / Pass on measured inputs |
| 异星工厂：科技树 | 0.447671 | 0.376580 | 43.34 | 36.67 | 已测输入通过 / Pass on measured inputs |
| 二叉树遍历 | 0.200720 | 0.207337 | 24.30 | 28.08 | 已测输入通过 / Pass on measured inputs |
原始计时、输入与源码哈希：R15。 / Timings and input/source hashes: R15.
随机交换的三种递推 / Recurrences for random swaps¶
期望版与概率版采用相同十份输入。所有程序均通过已测输入的 0.5 秒参考时限。期望版的仿射更新为线性轮次处理，直接期望与逐元素转移分别为平方与立方时间；概率版以指示变量逐列计算，达到输出所需的平方时间阶。固定模数下，两次快速幂的代价不随数组规模增长。
Both versions use the same ten inputs. Every supplied program meets the 0.5-second reference limit on these measured inputs. Affine updates process expectations in linear time, compared with quadratic direct expectations and cubic element propagation. Indicator columns compute the full matrix in quadratic time, matching its output size. With the fixed modulus, inverse computation does not grow with the array size.
| 题目 / Problem | 算法 / Algorithm | 最慢中位数 / Largest median (s) | 峰值 / Peak (MiB) |
|---|---|---|---|
| 随机分析：期望 | 全局仿射维护 / Global affine updates | 0.030652 | 5.31 |
| 随机分析：期望 | 直接期望递推 / Direct expectations | 0.032607 | 5.33 |
| 随机分析：期望 | 逐元素概率转移 / Element probabilities | 0.054410 | 5.32 |
| 随机分析：概率 | 指示变量与仿射维护 / Indicators with affine updates | 0.035418 | 5.99 |
| 随机分析：概率 | 逐元素概率转移 / Element probabilities | 0.059872 | 6.01 |
五轮计时、工作集、输入与源码哈希见完整测量。当前范围内的耗时包含启动与输入输出开销，复杂度优势不等于同等比例的实测加速。
See the full measurements for all five rounds, memory and hashes. Startup and I/O contribute to these timings; asymptotic improvements do not imply proportional speedups at the current size.
R16：四组实现比较 / Four implementation pairs¶
四题各两份程序在相同正式输入上交替运行五轮，结果一致。纸老虎序列的分段回溯程序以最多 64 KiB 字符缓存减少存储，作为并列方案。简单火车的 Borůvka 程序展示按分量合并的不同策略；积木塔的按步号构造和电路板的直接求值作为备用实现。
Each pair agrees on the same formal inputs over five alternating rounds. Paper Tiger's interval output uses at most 64 KiB of character cache and is retained as a parallel space-saving option. Borůvka demonstrates component-based merging for the rail graph. Indexed Hanoi construction and direct predicate evaluation are backup implementations.
| 题目 / Problem | 标程 / Reference (s) | 补充 / Alternative (s) | 标程 / Reference (MiB) | 补充 / Alternative (MiB) | 状态 / Status |
|---|---|---|---|---|---|
| 纸老虎序列 | 0.070396 | 0.069889 | 9.04 | 5.36 | 已测输入通过 / Measured inputs pass |
| 异星工厂：简单火车 | 0.710041 | 0.747512 | 35.69 | 39.52 | 已测输入通过 / Measured inputs pass |
| 积木塔 | 0.029726 | 0.031369 | 5.31 | 5.30 | 已测输入通过 / Measured inputs pass |
| 异星工厂：测试电路板 | 0.027496 | 0.028904 | 5.32 | 5.32 | 已测输入通过 / Measured inputs pass |
时间包括进程启动与输入输出，内存为峰值工作集。纸老虎覆盖最大最终长度及全部版本输出；铁路覆盖百万顶点、两百万条边、负自环、重边、不连通图和多轮合并构造。完整轮次、种子配方对应的输入及程序哈希见 R16。
Timings include startup and I/O; memory is peak working set. Paper Tiger includes maximum growth and all-version output. Rail inputs cover a million vertices, two million edges, negative loops, parallel edges, disconnected graphs and multiple merging rounds. Full runs and hashes are in R16.
分拣、环形操作与因数计数 / Parsing, ring operations and divisor counting¶
每题的两份程序在相同的十份正式输入上交替测量五轮，并与独立程序计算的答案核对。六份程序均通过 0.5 秒参考时限。流式分拣省去完整输入串；环形链表有确定的短步数界，隐式 Treap 将移动改为排名运算；候选因数检查使用较少空间，因数计数给出不含逐候选全数组扫描的时间界。
Each pair was measured over five alternating rounds on the same ten formal inputs and checked against an independent oracle. All six programs meet the 0.5-second reference limit. Streaming avoids storing the complete input string. The linked ring has deterministic short-movement bounds, while the implicit treap moves by rank. Candidate testing uses less space; divisor counting avoids a complete array scan for each candidate in its time bound.
| 题目 / Problem | 标程 / Reference (s) | 补充 / Alternative (s) | 标程 / Reference (MiB) | 补充 / Alternative (MiB) |
|---|---|---|---|---|
| 异星工厂：分拣流水线 | 0.029646 | 0.029030 | 5.61 | 5.43 |
| 异星工厂：机器人指令平台 | 0.130818 | 0.055661 | 6.71 | 9.77 |
| 猜公因子 | 0.156365 | 0.112210 | 13.90 | 5.32 |
因数计数的较好最坏时间结构不等于这些输入上更快；候选检查程序在本组输入上的最慢中位数更小、峰值工作集也更低，作为并列方案保留。高因数数量用例包含 1000 个 735134400；低命中用例包含大素数、平方数及后部集中的可整除项。计时包括启动与输入输出。完整轮次、输入、源码、生成计划及可执行文件哈希见 R17。
The different worst-case time structure of divisor counting does not imply faster execution on these inputs. Candidate testing has a smaller largest median and lower peak working set here and is retained as a parallel option. The divisor-count stress includes 1000 copies of 735134400. Other inputs include large primes, squares, and divisible entries concentrated near the end. Timings include startup and I/O. See R17 for every run and input, source, recipe and binary hashes.
公式、交集与序列操作 / Formulas, intersections and sequence operations¶
六题各有十份正式输入，全部程序与独立答案核对一致，并交替计时五轮。十三份程序均通过 0.5 秒参考时限。下表记录各程序最慢用例的中位耗时及独立测得的最大峰值工作集。
Each problem has ten formal inputs. All programs agree with independent answers and were measured over five alternating rounds. All thirteen programs meet the 0.5-second reference limit. The table reports the largest per-input median and separately measured maximum peak working set.
| 题目 / Problem | 算法 / Algorithm | 最慢中位数 / Largest median (s) | 峰值 / Peak (MiB) |
|---|---|---|---|
| 星际订单：加速度 | 整数半单位 / Integer half-units | 0.026736 | 5.33 |
| 星际订单：矩形相交 | 上边界分类 / Upper-edge cases | 0.028026 | 5.32 |
| 星际订单：矩形相交 | 投影相交 / Projection overlap | 0.029381 | 5.32 |
| 星际订单：矩形相交 | 中心距离 / Center distances | 0.029282 | 5.32 |
| 星际订单：交集分类 | 上边界与维数 / Upper edges and dimensions | 0.028374 | 5.32 |
| 星际订单：交集分类 | 投影相交 / Projection overlap | 0.029823 | 5.32 |
| 星际订单：交集分类 | 中心距离 / Center distances | 0.029224 | 5.32 |
| 异星工厂：搅拌机 | 直接矩阵 / Direct matrix | 0.050415 | 5.32 |
| 异星工厂：搅拌机 | 行列索引 / Row and column indices | 0.049254 | 5.32 |
| 疯狂的串串 | KMP | 0.033788 | 5.33 |
| 疯狂的串串 | 截取后连续查找 / Extract and find | 0.034423 | 5.35 |
| 优选猫咪 | 按选择数 DP / DP by selection count | 0.027754 | 5.32 |
| 优选猫咪 | 子集搜索 / Subset search | 0.048333 | 5.32 |
矩形的三种方法都以常数时间处理每组输入。搅拌机的索引方案减少旋转时的数据搬移，但每次合法操作都要输出整个矩阵，因此总时间仍受输出量约束。KMP 的最坏时间界较好；选猫动态规划合并重复状态，搜索程序也能通过当前规模。小幅耗时差异包含进程启动与输入输出开销，不能据此推断稳定的算法速度差。
All three rectangle methods take constant time per pair. The mixer's index representation reduces cell movement during rotation, while printing every valid state still determines the total output cost. KMP has a stronger worst-case time bound. Cat-selection DP merges repeated states, and subset search also meets the current limit. Small timing differences include startup and I/O and do not establish a stable algorithm speed advantage.
完整轮次、输入、源码、生成计划及可执行文件哈希见 R18。 / All runs and input, source, recipe and binary hashes are in R18.
字符输出、递归与环形状态 / Character output, recursion and circular state¶
六题各十份正式输入，所有程序均与独立答案核对，并进行五轮交替计时。十三份程序都通过 0.5 秒参考时限。下表的时间与内存分别取最大用例中位数和最大峰值工作集，不一定来自同一输入。
Each problem has ten formal inputs. All programs were checked against independent answers and measured over five alternating rounds. All thirteen meet the 0.5-second reference limit. Time and memory are the largest per-input median and largest peak working set, which may come from different inputs.
| 题目 / Problem | 算法 / Algorithm | 最慢中位数 / Largest median (s) | 峰值 / Peak (MiB) |
|---|---|---|---|
| 字符 X | 逐格斜带判定 / Diagonal-strip tests | 0.027682 | 5.30 |
| 字符 X | 固定模板 / Fixed template | 0.027276 | 5.30 |
| 递归训练：最大值 | 逐项递归 / Prefix recursion | 0.028197 | 5.31 |
| 递归训练：最大值 | 平衡递归 / Balanced recursion | 0.028860 | 5.31 |
| 无限二叉树上的距离 | 较大编号上移 / Larger-label ascent | 0.067031 | 5.32 |
| 无限二叉树上的距离 | 深度对齐 / Depth alignment | 0.067339 | 5.32 |
| 变量列表 | 双向指针链表 / Doubly linked lists | 0.227879 | 35.70 |
| 滴嘟hia的能指循环 | 当前路径 / Current walk | 0.035709 | 6.88 |
| 滴嘟hia的能指循环 | 访问时间戳 / Visit timestamps | 0.032429 | 6.08 |
| 滴嘟hia的能指循环 | 入度剥离 / Indegree pruning | 0.033281 | 6.53 |
| 滴嘟hia的能指循环 | 映射倍增 / Mapping doubling | 0.034734 | 6.09 |
| 异星工厂：信号网络 | 两个无符号字 / Two unsigned words | 0.231701 | 5.31 |
| 异星工厂：信号网络 | 循环起点与线段树 / Circular origin and segment tree | 0.316862 | 5.32 |
递归最大值的平衡方案降低调用栈深度，两者仍保存完整输入数组；题目的递归实现要求另由源代码检查确认。函数图时间戳方案省去当前路径及独立访问标记，实测峰值也更小；倍增方案具有更高的时间增长阶，但通过当前规模。信号网络的两字实现和环形线段树均覆盖两百万次操作、负旋转、零旋转及跨字取反。小幅耗时差包含启动和输入输出开销。
Balanced maximum recursion reduces call-stack depth; both implementations still store the entire input array. Source inspection separately confirms the recursion requirement. Functional-graph timestamps eliminate the current path and separate visited flags, and also have a lower measured peak. Doubling has a higher time-growth order but meets the current limit. Both signal implementations cover two million operations, negative and zero rotations, and flips crossing word boundaries. Small timing differences include startup and I/O overhead.
完整轮次、输入、源码、程序及配方哈希见 R19。 / Full runs and input, source, binary and recipe hashes are in R19.
数位、传递与采购计数 / Digits, passing and purchase counting¶
三题各十份正式输入，六份程序均完成独立核对与五轮交替计时。参考时限均为0.5秒。时间包含进程启动与输入输出，表中峰值为最大工作集。
Each of the three problems has ten formal inputs. All six programs were independently checked and timed in five alternating rounds. All reference limits are 0.5 seconds. Times include process startup and I/O; peaks are the largest measured working sets.
| 题目 / Problem | 程序 / Program | 最慢中位数（秒） / Largest median (s) | 峰值 / Peak (MiB) |
|---|---|---|---|
| 旋涡数 | std.cpp | 0.029017 | 5.31 |
| 旋涡数 | alternative.cpp | 0.030038 | 5.31 |
| 横版场域论 | std.cpp | 0.033692 | 5.46 |
| 圣辇船直营菓子工房的补货 | std.cpp | 0.028781 | 5.27 |
| 圣辇船直营菓子工房的补货 | alternative-knapsack.cpp | 0.030332 | 5.27 |
| 圣辇船直营菓子工房的补货 | alternative-search.cpp | 0.409648 | 5.25 |
多数用例较小，启动开销占比很高，几毫秒差异不能证明算法实际更快。补货的搜索备用程序约0.410秒，仅有约1.22倍余量，未达到建议的两倍余量；部署时不保证其通过完整数据。五边形数递推和完全背包均有充足余量。
Most inputs are small, and startup dominates; millisecond differences do not establish a practical speed advantage. Restocking search takes about 0.410 seconds and has only about 1.22 times headroom, below the suggested factor of two. Its full-range acceptance on deployment is not guaranteed. The pentagonal and knapsack methods have ample headroom.
逐次计时、输入与源码哈希见 R20。 / Individual runs and input/source hashes are in R20.
双端括号、置换与最短路 / Deque brackets, permutations and shortest paths¶
R21的五题各十份正式输入，8份C++17程序均完成独立核对与五轮交替计时。时间含启动和I/O；内存列为最大工作集，五题均保留128 MB。 此表的糖果括号为非负权版本；当前带负权版本的测量见下方“糖果括号：带负权”一节。
All five R21 problems have ten formal inputs. Eight C++17 programs were independently checked and timed in five alternating rounds. Times include startup and I/O; memory is the largest measured working set. Every problem retains its 128 MB limit. The Candy Brackets row here describes the nonnegative version; current signed-weight measurements appear in the section “Candy Brackets with signed weights” below.
| 题目 / Problem | 程序 / Program | 最慢中位数 / Largest median (s) | 峰值 / Peak (MiB) | 预估时限 / Limit (s) |
|---|---|---|---|---|
| 糖果括号（非负权） / Candy Brackets (nonnegative) | std.cpp | 0.394769 | 41.66 | 1 |
| 烤墨鱼的置换 | std.cpp | 0.098066 | 12.81 | 0.5 |
| 网格生存概率 | std.cpp | 0.145552 | 22.37 | 0.5 |
| 网格生存概率 | alternative.cpp | 0.248352 | 40.26 | 0.5 |
| 终点和起点 | std.cpp | 0.575196 | 47.04 | 1.5 |
| 终点和起点 | alternative.cpp | 0.537960 | 43.73 | 1.5 |
| 两类最短路查询 | std.cpp | 0.426403 | 37.51 | 1 |
| 两类最短路查询 | alternative.cpp | 0.428008 | 37.52 | 1 |
网格道路图方案在稀疏道路上减少每轮扫描，但在稠密图中有建图与邻接开销；其最慢中位数约0.248秒，在0.5秒时限下接近两倍余量。按查询起点分组的方法也受起点数影响，不作无条件更快的结论。没有测得与过慢程序的稳定分离；换平台或语言必须重新校准。
The road-graph method scans fewer states on sparse grids, but has graph-construction and adjacency costs on dense grids. Its largest median is about 0.248 seconds, giving close to twofold headroom under 0.5 seconds. Grouped-source searches also depend on the number of sources and are not unconditionally faster. No stable separation from a slow program was measured; other platforms and languages require recalibration.
逐次结果、编译配置及哈希见 R21。 / Individual measurements, compiler configuration and hashes: R21.
扑克阵容、格与精确递推 / Card lineups, lattices and exact recurrence¶
R22五题共66份正式输入，10份C++17程序通过独立核对及五轮交替计时。子格保留23份历史数据形状，并加入3份零分合法范围压力数据；其余题各10份。时间含启动和I/O，内存为另测峰值工作集，均保留128 MB。
R22 has 66 formal inputs and ten C++17 programs, independently checked and timed in five alternating rounds. Sublattice counting preserves 23 historical test shapes and adds three zero-score stress cases within the original bounds; each other problem has ten cases. Time includes startup and I/O; memory is separately measured peak working set. All retain 128 MB.
| 题目 / Problem | 程序 / Program | 最慢中位数 / Largest median (s) | 峰值 / Peak (MiB) | 预估时限 / Limit (s) |
|---|---|---|---|---|
| 红心女王的扑克士兵 | std.cpp | 0.296219 | 17.12 | 1 |
| 红心女王的扑克士兵 | alternative.cpp | 0.489427 | 21.25 | 1 |
| 拨号关系的补全 | std.cpp | 0.052308 | 6.83 | 0.5 |
| 拨号关系的补全 | alternative.cpp | 0.060155 | 7.86 | 0.5 |
| 识别符号格 | std.cpp | 0.851544 | 5.33 | 2 |
| 识别符号格 | alternative.cpp | 0.515953 | 5.31 | 2 |
| 子格计数 | std.cpp | 0.444016 | 5.32 | 1 |
| 子格计数 | alternative.cpp | 0.084858 | 25.18 | 1 |
| 子格计数 | brute.cpp | 0.777159 | 5.31 | 1 |
| 分数次幂递推 | std.cpp | 0.730355 | 81.87 | 1.5 |
扑克Fenwick方案约0.489秒，在1秒时限下余量接近两倍，没有无条件性能优势。子格子集DP以约20 MiB数组换取实测速度，保留原搜索为省空间首选；brute约0.777秒，只有约1.29倍余量，作为核对备份。未证明与低效程序的稳定分离；目标平台或语言改变时应重测。
The card Fenwick method takes about 0.489 seconds, with close to twofold headroom under one second and no unconditional speed advantage. Sublattice subset DP spends about 20 MiB on arrays for a measured speed gain; the original search remains the space-efficient reference. Its brute checker takes about 0.777 seconds, giving only 1.29 times headroom, and is retained as a verification backup. No stable separation from inefficient programs was established; remeasure for other platforms or languages.
逐次测量、配置与哈希 / Individual measurements, configuration and hashes: R22.
模求和、双链与分拆 / Modular sums, paired strands and partitions¶
R23五题各10份正式输入，9份C++17程序通过独立核对、样例及五轮交替计时。时间含启动和I/O；内存为另测峰值工作集，五题均保留128 MB。
Each R23 problem has ten formal inputs. Nine C++17 programs passed independent checks, samples, and five alternating timing rounds. Times include startup and I/O; memory is separately measured peak working set. All five retain 128 MB.
| 题目 / Problem | 程序 / Program | 最慢中位数 / Largest median (s) | 峰值 / Peak (MiB) | 预估时限 / Limit (s) |
|---|---|---|---|---|
| 某不科学的等差等比加权和 | std.cpp | 0.137502 | 5.32 | 0.5 |
| 某不科学的等差等比加权和 | alternative.cpp | 0.129558 | 5.32 | 0.5 |
| 某不科学的多重前缀求和 | std.cpp | 0.072989 | 5.31 | 0.5 |
| 某不科学的多重前缀求和 | alternative.cpp | 0.081463 | 5.97 | 0.5 |
| DNA 双链序列计数 | std.cpp | 0.130325 | 5.33 | 0.5 |
| DNA 双链序列计数 | alternative.cpp | 0.067693 | 5.67 | 0.5 |
| 多类配对的 DNA 双链计数 | std.cpp | 0.243633 | 5.33 | 0.5 |
| 无标号容器分配 | std.cpp | 0.032774 | 5.33 | 0.5 |
| 无标号容器分配 | alternative.cpp | 0.036205 | 5.33 | 0.5 |
幂表减少大量固定底数查询的耗时，但使用额外表空间；二进制幂仍是省空间首选。分拆的五边形方法在m接近n时更快，m很小时背包更合适。广义双链标准程序约0.244秒，在0.5秒时限下接近两倍余量。没有稳定排除所有低效方法的测量结论；其他平台或语言需重测。
Power tables speed up many fixed-base queries at an extra storage cost; binary exponentiation remains the space-efficient reference. The pentagonal partition method is faster when m is close to n, while knapsack suits small m. The general paired-strand reference takes about 0.244 seconds, with close to twofold headroom under 0.5 seconds. No stable exclusion of every inefficient method was established; remeasure on other platforms or languages.
逐次记录与哈希 / Individual measurements and hashes: R23.
等比求和、序列与构造 / Geometric sums, sequences and constructions¶
R24五题，共49份正式输入、8份C++17程序，每例每程序五轮交替计时，均保留128 MB。树计数保留精确三等分，使用9份数据；其余各10份。时间含启动与I/O，内存另测峰值工作集。
Five R24 problems have 49 formal inputs and eight C++17 programs. Each program/case was timed five times in alternating order. All retain 128 MB. Tree counting preserves exact thirds with nine cases; the others have ten each. Times include startup and I/O; peak working set is measured separately.
| 题目 / Problem | 程序 / Program | 最慢中位数 / Largest median (s) | 峰值 / Peak (MiB) | 时限 / Limit (s) |
|---|---|---|---|---|
| 某不科学的多重等比求和 | std.cpp | 0.043647 | 12.81 | 0.5 |
| Grox的序列一 | std.cpp | 0.059213 | 6.71 | 0.5 |
| Grox的序列一 | alternative.cpp | 0.094421 | 9.94 | 0.5 |
| 平方和球柱 | std.cpp | 0.044277 | 5.31 | 0.5 |
| 平方和球柱 | alternative.cpp | 0.050909 | 9.11 | 0.5 |
| 平方和球柱的容量 | std.cpp | 0.141392 | 7.73 | 0.5 |
| 平方和球柱的容量 | alternative.cpp | 0.199319 | 8.82 | 0.5 |
| 按顺序连成树 | std.cpp | 0.030137 | 5.26 | 0.5 |
Grox系数递推省去NTT及二次式展开；球柱按列输出节省保存方案的空间。高精度容量保留NTT首选，Karatsuba展示无需模数的分治整数平方。所有程序均支持完整数据且有至少两倍实测余量；不据此宣称排除了所有其他算法，换平台须重测。
The Grox coefficient recurrence removes NTT and quadratic expansion. Column streaming saves arrangement storage. Exact capacity keeps NTT as its reference, with Karatsuba providing a divide-and-conquer integer alternative without a modulus. Every program supports all cases with at least twofold measured headroom. This does not exclude all other algorithms; remeasure on another platform.
逐次记录与哈希 / Individual measurements and hashes.
选址、路线与树统计 / Placement, routes and tree counts¶
R25五题、50份正式输入、9份C++17程序。每例每程序五轮交替测量，时间含启动和I/O，峰值工作集另测。前三题保留128MB，区间栈与树统计保留512MB。输入规模和边界以各题题面为准。
Five R25 problems provide 50 formal inputs and nine C++17 programs. Every case/program was timed five times in alternating order, including startup and I/O. Peak working set was measured separately. The first three problems retain 128 MB; the interval-stack and tree-count problems retain 512 MB.
| 题目 / Problem | 程序 / Program | 最慢中位数 / Largest median (s) | 峰值 / Peak (MiB) | 倍率 / Multiplier | 时限 / Limit (s) |
|---|---|---|---|---|---|
| 直线上的服务站 | std.cpp | 0.046758 | 5.13 | 2 | 0.5 |
| 直线上的服务站 | alternative.cpp | 0.068522 | 35.61 | 2 | 0.5 |
| 下坡路线计数 | std.cpp | 0.033733 | 10.38 | 2 | 0.5 |
| 有限体力的路线计数 | std.cpp | 0.162161 | 12.00 | 2 | 0.5 |
| 小Y的线段树 | std.cpp | 0.136456 | 16.46 | 10 | 1.5 |
| 小Y的线段树 | alternative.cpp | 0.242011 | 29.82 | 10 | 1.5 |
| 小Y的线段树 | alternative-binary-lifting.cpp | 0.661415 | 48.88 | 10 | 1.5 |
| 祖先子树的分层统计 | std.cpp | 6.828211 | 350.38 | 2 | 14 |
| 祖先子树的分层统计 | alternative.cpp | 5.505307 | 157.64 | 2 | 14 |
区间栈采用倍率10：前驱倍增允许不存查询、逐条回答，其最大中位数0.661415秒，需要至少1.32283秒的两倍余量；标准程序0.136456秒乘10后按0.5秒取整得到1.5秒。其余题使用默认倍率2。所有程序均在完整范围内有至少两倍实测通过余量。树题重链程序在这组数据上的实测时间、内存均低于点分治，但点分治具有更好的最坏时间复杂度；两种方法并列说明。
The interval-stack problem uses multiplier 10: its streaming-query binary-lifting implementation has a largest median of 0.661415 seconds, requiring at least 1.32283 seconds for twofold headroom. Multiplying the reference's 0.136456 seconds by ten and rounding to 0.5-second increments gives 1.5 seconds. Other problems use the default multiplier two. All programs have at least twofold measured headroom on the full constraints. For tree counts, heavy-light decomposition uses less measured time and memory on these cases, while centroid decomposition has a better worst-case time bound; both are presented as full-scope choices.
没有对过慢程序做分离实验，不能由这些数据推出所有低效算法都会超时。跨平台须重新校准。
No slow-program separation experiment is claimed. These measurements do not establish that every inefficient algorithm will time out. Recalibrate on other platforms.
逐次记录与哈希 / Individual timings and hashes.
牌组、递推与区间和 / Tiles, recurrences and subarray sums¶
五题共有50份正式输入、8份C++17程序，每份输入与程序交替测量五轮，包含启动和I/O。保留题面规定的128、512、2048或1024MB内存，输入范围没有加强或缩小。
These five problems have 50 formal inputs and eight C++17 programs, each timed five times in alternating order, including startup and I/O. Their specified memory limits of 128, 512, 2048 or 1024 MB and all original input ranges are retained.
| 题目 / Problem | 程序 / Program | 最慢中位数 / Largest median (s) | 峰值 / Peak (MiB) | 倍率 / Multiplier | 时限 / Limit (s) |
|---|---|---|---|---|---|
| 不同顺子的牌组划分 | std.cpp | 0.738286 | 81.28 | 2 | 1.5 |
| 牌组前缀的可行划分 | std.cpp | 0.139151 | 5.12 | 2 | 0.5 |
| 老yd与并查集 | std.cpp | 0.498705 | 157.57 | 4 | 2 |
| 老yd与并查集 | alternative.cpp | 0.989182 | 43.13 | 4 | 2 |
| 最小值加权的区间和 | std.cpp | 0.573746 | 233.86 | 2 | 1.5 |
| 最小值加权的区间和 | alternative.cpp | 0.350686 | 233.86 | 2 | 1.5 |
| 端倪发生器 | std.cpp | 1.166497 | 133.56 | 2 | 2.5 |
| 端倪发生器 | alternative.cpp | 0.696825 | 12.63 | 2 | 2.5 |
无理数递推使用倍率4：单逆元表方案最慢中位数0.989182秒，需要至少1.978364秒的两倍余量；标准程序0.498705秒乘4后向上取整为2秒。它的工作集约43MiB，阶乘表方案约158MiB。其余题默认倍率2，所有发布程序至少有两倍余量并通过原内存要求。零和查询的二分方案工作集约13MiB，矩阵方案约134MiB，运行差异取决于数值分布与缓存访问。
The recurrence uses multiplier four: the single-inverse-table option's largest median is 0.989182 seconds, requiring at least 1.978364 seconds for twofold headroom. Multiplying the reference's 0.498705 seconds by four and rounding upward gives two seconds. Its working set is about 43 MiB versus 158 MiB for factorial tables. Other problems use the default multiplier two. All published programs have at least twofold headroom and satisfy the original memory limits. For zero-sum queries, binary searches use about 13 MiB versus 134 MiB for the matrix; timing differences depend on value distribution and cache access.
没有据此宣称排除所有其他算法，跨平台和语言须重新校准。
These measurements do not exclude all other algorithms; recalibrate for different platforms and languages.
逐次记录与哈希 / Individual timings and hashes.
数位、栈、搜索树与路径 / Digits, stacks, search trees and routes¶
五题50份正式输入、6份C++17程序，每个输入/程序交替测量五轮，包含启动与I/O。原范围、128/512/4096MB内存均保留。
These five problems have 50 formal inputs and six C++17 programs, timed five times per input and program in alternating order, including startup and I/O. All input ranges and the original 128/512/4096 MB limits are retained.
| 题目 / Problem | 程序 / Program | 最慢中位数 / Largest median (s) | 峰值 / Peak (MiB) | 倍率 / Multiplier | 时限 / Limit (s) |
|---|---|---|---|---|---|
| 数位合并的最大值与最小值 | std.cpp | 0.097197 | 8.82 | 2 | 0.5 |
| 用多个栈实现队列 | std.cpp | 0.069940 | 13.01 | 2 | 0.5 |
| 保留形状的二叉搜索树 | std.cpp | 0.040310 | 8.13 | 2 | 0.5 |
| 字典序最大的树标号 | std.cpp | 0.537515 | 121.69 | 4 | 2.5 |
| 字典序最大的树标号 | alternative.cpp | 1.042603 | 121.43 | 4 | 2.5 |
| 转动的字节 | std.cpp | 1.938049 | 176.66 | 2 | 4 |
树标号题使用倍率4：主程序最慢中位数0.537515秒，静态祖先集合排序1.042603秒，2.5秒为两种方案保留至少两倍实测余量。其余题倍率2。未为补充方案缩小范围，所有程序均满足原内存。跨平台和语言须重新校准，不据此排除未测算法。
The heap-labeling problem uses multiplier four: its reference's largest median is 0.537515 seconds and static ancestor-set sorting takes 1.042603 seconds. A 2.5-second limit gives both at least twofold measured headroom. Other problems use multiplier two. No ranges are reduced for alternatives, and all programs satisfy original memory limits. Recalibrate for other platforms or languages; untested algorithms are not excluded by these measurements.
逐次记录与哈希 / Individual timings and hashes.
拆除、运输、匹配与动态计数 / Scheduling, transport, matching and counting¶
五题50份正式配方、7份C++17程序，每个输入/程序交替测量五轮，包含启动与I/O。全部保留原范围和128/512MB内存。
These five problems have 50 formal recipes and seven C++17 programs. Each input/program is timed five times in alternating order, including startup and I/O. Original ranges and 128/512 MB memory limits are preserved.
| 题目 / Problem | 程序 / Program | 最慢中位数 / Largest median (s) | 峰值 / Peak (MiB) | 倍率 / Multiplier | 时限 / Limit (s) |
|---|---|---|---|---|---|
| 树上设备的拆除顺序 | std.cpp | 0.528222 | 46.04 | 2 | 1.5 |
| 直线上的容量运输 | std.cpp | 0.114284 | 21.87 | 18 | 2.5 |
| 直线上的容量运输 | alternative-blocks.cpp | 1.071360 | 12.98 | 18 | 2.5 |
| 时间管理与多人运动 | std.cpp | 2.176987 | 6.20 | 2 | 4.5 |
| 动态二进制约束计数 | std.cpp | 0.214605 | 35.48 | 2 | 0.5 |
| 一类四邻接网格图森林的匹配问题 | std.cpp | 0.049681 | 6.65 | 11 | 1 |
| 一类四邻接网格图森林的匹配问题 | alternative-bitsets.cpp | 0.379284 | 5.15 | 11 | 1 |
运输题倍率18得到2.5秒，网格题倍率11得到1秒，使分块和位集补充方案都至少有两倍实测余量。其余倍率2。运输的符号线段树未声称对数摊还更新，网格的未证三次方界也未当作定理；题解分别提供可证明的参数化界。完整范围测试不等于覆盖所有最坏输入形状。
Transport uses multiplier18 and 2.5 seconds; the grid walk uses multiplier11 and one second. These give the block and bitset alternatives at least twofold measured headroom. Other multipliers are two. The explanations do not assert logarithmic amortized sign-tree updates or an unproved cubic grid bound; explicit provable workload bounds are provided. Full-range tests do not cover every possible worst-case shape.
逐次记录与哈希 / Individual measurements and hashes.
后缀排序、共同连通与精确路径 / Suffix sorting, common connectivity and exact paths¶
五题50份正式配方、7份C++17程序，每个输入和程序交替计时五次。原256/512/128MB内存和输入范围保留；所有倍率为2。
These five problems have 50 formal recipes and seven C++17 programs. Each input and program is timed five times in alternating order. Original ranges and 256/512/128 MB limits are retained; all multipliers are two.
| 题目 / Problem | 程序 / Program | 最慢中位数 / Largest median (s) | 峰值 / Peak (MiB) | 倍率 / Multiplier | 时限 / Limit (s) |
|---|---|---|---|---|---|
| 选择后缀元素的排序 | std.cpp | 0.098839 | 15.19 | 2 | 0.5 |
| 多棵树中的共同连通集 | std.cpp | 1.417158 | 16.76 | 2 | 3 |
| 二的幂拆分计数 | std.cpp | 0.028983 | 6.46 | 2 | 0.5 |
| 战斗属性的升级计划 | std.cpp | 1.318113 | 328.52 | 2 | 3 |
| 战斗属性的升级计划 | alternative-heap.cpp | 1.161873 | 120.00 | 2 | 3 |
| 动态树中的路径独立性 | std.cpp | 0.710847 | 109.04 | 2 | 1.5 |
| 动态树中的路径独立性 | alternative-offline.cpp | 0.203108 | 31.15 | 2 | 1.5 |
多树连通的保守Dinic上界与实际网络结构有关，题解没有宣称对数最大流。战斗题用精确整数处理超过64位的中间桶值；堆调度减少事件存储。动态路径的在线规范块和离线排序均为精确方法，离线版需预读输入。所有补充程序具有至少两倍实测时间余量。
The common-tree solution states a conservative Dinic bound rather than logarithmic flow time. Battle upgrades handle intermediate bucket values beyond 64 bits exactly, with heap scheduling reducing event storage. Both online canonical blocks and offline ranks give exact path comparisons; the latter requires the full input in advance. All alternatives retain at least twofold measured time headroom.
逐次记录与哈希 / Individual measurements and hashes.
糖果括号：带负权 / Candy Brackets with signed weights¶
权值范围为 [-4000000000, 4000000000]，N、M 均不超过 1000000。20 份正式输入各完成独立答案核对、重复生成比对和五轮计时；峰值工作集另测。参考环境与 R21 使用相同的 CPU、系统和编译选项，逐次结果及源码、生成器、配方和数据哈希见带负权测量。
Weights range from -4000000000 to 4000000000, with N and M each at most 1000000. All 20 formal inputs were independently checked, regenerated for byte comparison and timed five times; peak working set was measured separately. The CPU, system and compiler flags match R21. See the signed-weight measurements for individual runs and source, generator, plan and data hashes.
| 题目 / Problem | 程序 / Program | 最慢中位数 / Largest median (s) | 峰值 / Peak (MiB) | 预估时限 / Limit (s) |
|---|---|---|---|---|
| 糖果括号 | std.cpp | 0.383283 | 86.92 | 1 |
时限取最慢中位数乘 2，并按 0.5 秒向上取整，得到 1 秒；内存限制为 128 MB。最大内存数据保留了 200 万个未匹配括号。独立校验使用离线括号层次与同层原子块激活，先与枚举子串比较，再核对全部正式输入。未测量过慢方案的稳定超时分离；其他平台和语言仍需校准。
Twice the largest median, rounded up to 0.5 seconds, gives a 1-second limit; the memory limit is 128 MB. The largest-memory case retains two million unmatched brackets. The independent oracle parses bracket levels offline and activates sibling atoms, first checking against substring enumeration and then checking every formal input. No stable timeout separation from slower algorithms was measured; other platforms and languages require recalibration.
R30 测量 / Measurements¶
参考环境与编译选项同上；每例计时五次。完整数据包含跨模数组合数、零权BST、深表达式和十万结点衣架链。
The environment and compiler flags are unchanged. Every case has five timing runs. Full-range inputs include coefficients crossing the modulus, zero-frequency trees, deep expressions, and 100,000-node hanger chains.
| 题目 / Problem | 程序 / Program | 最慢中位数 / Median (s) | 峰值 / Peak (MiB) | 时限 / Limit (s) |
|---|---|---|---|---|
| 某不科学的单调序列的首项加权和 | alternative.cpp | 0.072967 | 5.27 | 0.5 |
| 某不科学的单调序列的首项加权和 | std.cpp | 0.104429 | 5.26 | 0.5 |
| 某不科学的单调序列计数 | alternative.cpp | 0.033155 | 5.27 | 0.5 |
| 某不科学的单调序列计数 | std.cpp | 0.030528 | 5.25 | 0.5 |
| 最优二叉检索树 | alternative.cpp | 0.048035 | 8.04 | 0.5 |
| 最优二叉检索树 | std.cpp | 0.038921 | 8.04 | 0.5 |
| 作物解锁条件 | std.cpp | 0.049866 | 16.89 | 0.5 |
| 菱形衣架的排列 | alternative.cpp | 0.046359 | 6.19 | 0.5 |
| 菱形衣架的排列 | std.cpp | 0.049001 | 9.82 | 0.5 |
逐次时间、输入与程序哈希 / Timing and hashes。所有程序均通过本组完整配方；不以这些运行结果宣称排除所有较慢算法。
R31 测量 / Measurements¶
环境与编译选项同上，每例五次计时。包含完整十万字符表达式压力、百万数值选择、十万次区间计数，以及两千万项生成序列。
The environment and compiler flags are unchanged, with five timing runs per case. Tests cover expressions near the 100,000-character bound, selection among one million values, 100,000 range queries, and generated sequences of 20 million items.
| 题目 / Problem | 程序 / Program | 最慢中位数 / Median (s) | 峰值 / Peak (MiB) | 时限 / Limit (s) | 通过时限 / Within limit |
|---|---|---|---|---|---|
| 连续内存中的字符串函数 | alternative.cpp | 0.051858 | 5.34 | 0.5 | 是 / Yes |
| 连续内存中的字符串函数 | std.cpp | 0.042465 | 5.37 | 0.5 | 是 / Yes |
| 整数运算器 | std.cpp | 0.030337 | 5.52 | 0.5 | 是 / Yes |
| 最接近中位数的数 | alternative.cpp | 0.154899 | 12.79 | 0.5 | 是 / Yes |
| 最接近中位数的数 | std.cpp | 0.115108 | 12.81 | 0.5 | 是 / Yes |
| DNA 双链长度区间计数 | alternative.cpp | 0.082129 | 5.31 | 0.5 | 是 / Yes |
| DNA 双链长度区间计数 | std.cpp | 0.076774 | 5.32 | 0.5 | 是 / Yes |
| 生成序列中的预算选择 | alternative.cpp | 1.525428 | 81.46 | 1.0 | 否 / No |
| 生成序列中的预算选择 | std.cpp | 0.258953 | 81.48 | 1.0 | 是 / Yes |
逐次时间、峰值与哈希 / Timings, memory, and hashes。生成序列的排序程序全量结果正确，但超过当前时限；它作为备用与交叉验证程序，不将单份实现超时视为排除全部同阶算法的证据。
The sorting program for generated-budget selection produces correct full-range outputs but exceeds the current time limit. It is a backup and cross-check; this result does not rule out every algorithm with the same asymptotic complexity.
R32 测量 / Measurements¶
每例五次计时，另测峰值；编译环境与上文相同。密码、表达式和加密栈采用默认2倍。树的在线重心分解与补给的费用流具有不同用途，分别采用13倍、16倍以提供约两倍补充算法的实测余量。最终均向上取整到0.5秒。所有程序完整结果一致并通过公布时限与内存。
Five timing runs per case plus a separate peak-memory run use the environment above. Default multiplier 2 applies to passwords, expressions, and encrypted stacks. Multipliers 13 and 16 for tree diameters and refueling accommodate the distinct online centroid and flow methods with roughly twice their measured time. Limits round upward to 0.5 seconds. Both programs for every problem agree and pass the stated limits.
| 题目 / Problem | 程序 / Program | 最慢中位数 / Median (s) | 峰值 / Peak (MiB) | 时限 / Limit (s) |
|---|---|---|---|---|
| 使徒卢克的密码 | alternative.cpp | 0.137505 | 6.85 | 0.5 |
| 使徒卢克的密码 | std.cpp | 0.092540 | 5.32 | 0.5 |
| 大圣诞树 | alternative.cpp | 1.108494 | 262.25 | 2.5 |
| 大圣诞树 | std.cpp | 0.175889 | 27.55 | 2.5 |
| 带短路规则的运算器 | alternative.cpp | 0.050079 | 27.03 | 0.5 |
| 带短路规则的运算器 | std.cpp | 0.039843 | 21.79 | 0.5 |
| 老Y的线段树 | alternative.cpp | 0.072590 | 29.94 | 0.5 |
| 老Y的线段树 | std.cpp | 0.048399 | 9.00 | 0.5 |
| 限量补给的旅程 | alternative.cpp | 0.439161 | 5.86 | 1 |
| 限量补给的旅程 | std.cpp | 0.058527 | 5.45 | 1 |
原始测量及哈希 / Raw measurements and hashes。其他环境需重新测量。Recalibrate on other machines.
R33 测量 / Measurements¶
沿用上述环境，每例五次测时，另测峰值。全部题目按标准最慢中位数乘2，向上取整到0.5秒。标准均通过；排列Fenwick与动态和幂矩方案最大规模输出正确但超过时限，明确作为备用。两种交换构造按专用检查器验收，输出不要求相同。
The same environment uses five timing runs and a separate peak-memory run per case. Limits are twice the slowest standard median, rounded upward to 0.5 seconds. All standard programs pass. Fenwick permutation jumping and moment-based dynamic sums produce correct full-range results but exceed the limit and are backups. Both restoration constructions pass the output checker; their outputs may differ.
| 题目 / Problem | 程序 / Program | 最慢中位数 / Median (s) | 峰值 / Peak (MiB) | 时限 / Limit (s) | 通过时限 / Within limit |
|---|---|---|---|---|---|
| 排列的字典序跳转 | alternative.cpp | 0.740704 | 28.09 | 0.5 | 否 / No |
| 排列的字典序跳转 | std.cpp | 0.181389 | 12.81 | 0.5 | 是 / Yes |
| 叶子不区分的建树顺序 | std.cpp | 0.031118 | 6.79 | 0.5 | 是 / Yes |
| 指定叶子数的建树顺序 | std.cpp | 0.030520 | 6.79 | 0.5 | 是 / Yes |
| 交换之后的复原 | alternative.cpp | 0.062803 | 13.87 | 0.5 | 是 / Yes |
| 交换之后的复原 | std.cpp | 0.061549 | 10.95 | 0.5 | 是 / Yes |
| 某不科学的多项式加权几何和的修改 | alternative.cpp | 0.702457 | 5.54 | 0.5 | 否 / No |
| 某不科学的多项式加权几何和的修改 | std.cpp | 0.046044 | 5.86 | 0.5 | 是 / Yes |
逐次时间与哈希 / Individual timings and hashes。其他环境需重新测量，单个实现超时不排除全部同阶方法。Recalibrate elsewhere; one timed-out implementation does not exclude every method with its asymptotic complexity.
R34 测量 / Measurements¶
每例五次测时，另测峰值；标准最慢中位数乘2，向上取整到0.5秒。交互题通过真实管道运行提交程序，墙钟时间包含Python交互器和通信，峰值只计提交进程。充电桶模拟输出正确但超过时限，明确作为备用；其余标准及分块补充均通过。
Each case has five timing runs and a separate peak-memory run. Limits are twice the slowest standard median, rounded up to 0.5 seconds. The interactive submission runs through real pipes; wall time includes the Python judge and communication, while memory covers the submission only. The charging bucket simulation is correct but exceeds the limit and is a backup. All standard programs and the stack block alternative pass.
| 题目 / Problem | 程序 / Program | 最慢中位数 / Median (s) | 峰值 / Peak (MiB) | 时限 / Limit (s) | 通过时限 / Within limit |
|---|---|---|---|---|---|
| 可修改序列的单调栈 | alternative.cpp | 0.063319 | 5.62 | 0.5 | 是 / Yes |
| 可修改序列的单调栈 | std.cpp | 0.055566 | 6.90 | 0.5 | 是 / Yes |
| 共用充电器 | alternative.cpp | 0.737621 | 25.43 | 0.5 | 否 / No |
| 共用充电器 | std.cpp | 0.226576 | 19.33 | 0.5 | 是 / Yes |
| 树上的容限路径 | std.cpp | 0.330252 | 6.05 | 1 | 是 / Yes |
| 子串询问恢复排列 | std.cpp | 0.074435 | 5.28 | 0.5 | 是 / Yes |
| 这题是你自己出的 | std.cpp | 0.707113 | 30.11 | 1.5 | 是 / Yes |
逐次时间与哈希 / Individual timings and hashes。其他环境需重新测量；一份程序超时不排除全部同阶算法。Recalibrate elsewhere; one timed-out implementation does not exclude every algorithm with the same complexity.
R35 测量 / Measurements¶
每份正式数据各运行五次并另测峰值；标准程序最慢中位数乘2，向上取整到0.5秒。所有标准程序及后缀自动机补充均通过。矩形保持512 MiB，树维护保持512 MiB，巡检保持256 MiB，其余保持128 MiB。
Each formal input has five timing runs and a separate peak-memory run. Limits are twice the slowest standard median, rounded up to 0.5 seconds. All standard programs and the suffix-automaton alternative pass. Memory limits remain 512 MiB for rectangles and tree maintenance, 256 MiB for the road survey, and 128 MiB for the others.
| 题目 / Problem | 程序 / Program | 最慢中位数 / Median (s) | 峰值 / Peak (MiB) | 时限 / Limit (s) |
|---|---|---|---|---|
| 较小权不完美非匹配 | std.cpp | 0.100009 | 15.23 | 0.5 |
| 分批更新的矩形最大值 | std.cpp | 1.796455 | 234.07 | 4 |
| 唯一特征的命中期望 | alternative.cpp | 0.069435 | 80.46 | 0.5 |
| 唯一特征的命中期望 | std.cpp | 0.033904 | 7.22 | 0.5 |
| 心灵终结仪 | std.cpp | 0.403565 | 29.02 | 1 |
| 覆盖所有道路的巡检 | std.cpp | 0.584849 | 21.16 | 1.5 |
逐次时间与哈希 / Individual timings and hashes。其他环境需重新校准。Recalibrate in other environments.
R36 测量 / Measurements¶
每份正式文件计时五次并另测峰值，时限按标准最慢中位数乘2、向上取整到0.5秒。棋盘计算程序通过完整数据；下降乘积常数空间程序输出正确但最坏时间超过标准时限。传送带与棋盘采用8 MiB整进程限制：参考Windows仅运行常量输出也约占4.8 MiB，故不能声称满足4 MiB。其余题保持128 MiB。
Each formal file has five timings and a separate peak-memory run. Limits use twice the slowest standard median, rounded up to 0.5 seconds. The board calculator passes. The constant-space factorial program is correct but exceeds the full limit. Conveyor and board limits are 8 MiB for whole-process memory; the reference Windows runtime alone uses about 4.8 MiB, so it does not satisfy 4 MiB. Other limits remain 128 MiB.
| 题目 / Problem | 程序 / Program | 最慢中位数 / Median (s) | 峰值 / Peak (MiB) | 时限 / Limit (s) | 通过 / Pass |
|---|---|---|---|---|---|
| 限长传送带 | std.cpp | 0.363825 | 6.64 | 1 | 是 / Yes |
| 没有全黑直线的棋盘 | alternative.cpp | 0.013197 | 4.78 | 0.5 | 是 / Yes |
| 没有全黑直线的棋盘 | std.cpp | 0.012914 | 4.77 | 0.5 | 是 / Yes |
| 某不科学的立方盒中的最大公约数累计 | std.cpp | 0.825234 | 36.77 | 2 | 是 / Yes |
| 某不科学的单调序列的最大公约数之和 | std.cpp | 0.287184 | 36.46 | 1 | 是 / Yes |
| 某不科学的下降阶乘与二项式求和 | alternative.cpp | 1.963509 | 4.83 | 0.5 | 否 / No |
| 某不科学的下降阶乘与二项式求和 | std.cpp | 0.020536 | 4.83 | 0.5 | 是 / Yes |
逐次计时与哈希 / Timings and hashes。标准方案的离线阶乘检查点生成另需O(P)时间，不计入单次输入计时。The factorial table requires O(P) offline generation, excluded from per-input timings.
R37 测量 / Measurements¶
每份正式文件计时五次并另测峰值，时限按标准最慢中位数乘2、向上取整到0.5秒。五道标准程序通过；动态树弹跳方案答案一致，但超过参考时限，其优势是不依赖批次形状的摊还界。内存分别为128、512、128、2048、256 MiB。
Each formal input has five timings and a separate peak-memory run. Limits are twice the slowest standard median, rounded up to 0.5 seconds. All standard programs pass. Link-cut-tree jump answers agree, but its time exceeds the limit; its advantage is an amortized bound independent of batch shape. Memory limits are 128, 512, 128, 2048, and 256 MiB, respectively.
| 题目 / Problem | 程序 / Program | 最慢中位数 / Median (s) | 峰值 / Peak (MiB) | 时限 / Limit (s) | 通过 / Pass |
|---|---|---|---|---|---|
| 地牢房间的行为等价 | std.cpp | 0.070311 | 26.23 | 0.5 | 是 / Yes |
| 加密数据包与网络清空 | std.cpp | 0.611801 | 10.08 | 1.5 | 是 / Yes |
| 分批操作的向前弹跳 | alternative.cpp | 3.503765 | 9.50 | 0.5 | 否 / No |
| 分批操作的向前弹跳 | std.cpp | 0.199745 | 7.21 | 0.5 | 是 / Yes |
| 非交叉的1212子序列 | std.cpp | 0.068844 | 81.20 | 0.5 | 是 / Yes |
| 可修改环上的边权游戏 | std.cpp | 0.105521 | 11.42 | 0.5 | 是 / Yes |
逐次计时与哈希 / Timings and hashes。在其他环境重新校准。Recalibrate in other environments.
R38 测量 / Measurements¶
每份正式文件计时五次并另测峰值。全部标准程序与传送门补充程序均通过。内存限制依次为128、1024、128、512、512 MiB。
Each formal file has five timings and a separate peak-memory run. All references and the portal alternative pass. Memory limits are 128, 1024, 128, 512, and 512 MiB.
| 题目 / Problem | 程序 / Program | 最慢中位数 / Median (s) | 峰值 / Peak (MiB) | 时限 / Limit (s) |
|---|---|---|---|---|
| 花园的点击系数 | std.cpp | 0.041325 | 5.06 | 0.5 |
| 有限跨度的管道 | std.cpp | 0.531712 | 16.37 | 1.5 |
| 地狱门 | alternative-deadline.cpp | 0.035777 | 7.13 | 0.5 |
| 地狱门 | std.cpp | 0.020802 | 7.14 | 0.5 |
| 挖地铁 | std.cpp | 0.879732 | 62.59 | 2 |
| 白雪公主 | std.cpp | 1.204593 | 144.70 | 2.5 |
逐次计时与哈希 / Timings and hashes。在其他环境重新校准。Recalibrate in other environments.
R39 测量 / Measurements¶
每份正式文件计时五次并另测峰值，全部通过。参考内存限制128 MiB。 Each formal file has five timings and a separate peak-memory run. All pass; memory limit: 128 MiB.
| 题目 / Problem | 程序 / Program | 最慢中位数 / Median (s) | 峰值 / Peak (MiB) | 时限 / Limit (s) |
|---|---|---|---|---|
| 编辑城镇与模拟币 | std.cpp | 0.618839 | 12.56 | 1.5 |
逐次耗时与哈希 / Timings and hashes。在其他环境重新校准。Recalibrate in other environments.
R40 测量 / Measurements¶
每份正式文件计时五次并另测峰值。两种程序均通过，内存限制128 MiB；前向方案省去按最大初始人数建立的表。 Each formal file has five timings and a separate peak-memory run. Both programs pass the 128 MiB limit. The forward method omits tables indexed by the maximum initial household size.
| 题目 / Problem | 程序 / Program | 最慢中位数 / Median (s) | 峰值 / Peak (MiB) | 时限 / Limit (s) |
|---|---|---|---|---|
| 编辑城镇与模拟币2 | alternative-forward.cpp | 1.378412 | 12.56 | 2 |
| 编辑城镇与模拟币2 | std.cpp | 0.781932 | 27.82 | 2 |
逐次计时与哈希 / Timings and hashes。在其他环境重新校准。Recalibrate in other environments.
R41 测量 / Measurements¶
每份正式文件计时五次并另测峰值。两种程序均通过，内存限制64 MiB；输入包含最多100000份独立城镇存档。 Each formal input has five timings and a separate peak-memory run. Both implementations pass the 64 MiB limit. An input contains at most 100000 independent towns.
| 题目 / Problem | 程序 / Program | 最慢中位数 / Median (s) | 峰值 / Peak (MiB) | 时限 / Limit (s) |
|---|---|---|---|---|
| 编辑城镇与模拟币3 | alternative-affine.cpp | 0.104870 | 5.32 | 0.5 |
| 编辑城镇与模拟币3 | std.cpp | 0.104159 | 5.32 | 0.5 |
逐次耗时与哈希 / Timings and hashes。在其他环境重新校准。Recalibrate in other environments.
R42 测量 / Measurements¶
两题固定家庭位置总数，内存限制均为64 MiB。每份正式文件计时五次，并单独测量内存峰值；全部程序通过。两题的03至10号输入均含百万家庭位置。 Both problems have fixed household positions and a 64 MiB memory limit. Every formal file has five timings and a separate peak-memory run; all programs pass. Files 03–10 of both problems contain one million positions.
| 题目 / Problem | 程序 / Program | 最慢中位数 / Median (s) | 峰值 / Peak (MiB) | 时限 / Limit (s) |
|---|---|---|---|---|
| 编辑城镇与模拟币4 | std.cpp | 0.204831 | 13.64 | 0.5 |
| 编辑城镇与模拟币5 | alternative-forward.cpp | 0.142992 | 5.31 | 0.5 |
| 编辑城镇与模拟币5 | std.cpp | 0.140459 | 5.31 | 0.5 |
逐次耗时与哈希 / Timings and hashes。在其他环境重新校准。Recalibrate in other environments.
SC2：剑与暴击 / Swords and Critical Hits¶
本题使用本页的参考环境与编译选项；标程是独立的单文件 C++17 源码，仅使用有符号 64 位整数范围内的计算。十份正式输入逐份交叉核对输出，独立测量内存，并各计时五次。数据配方见测试说明，完整逐次记录见 SC2。
The self-contained C++17 reference uses only arithmetic within signed 64-bit range. All ten formal inputs are cross-checked and measured five times, with separate peak-memory runs, using the platform and flags above. See the test notes and SC2 for recipes, timings, and hashes.
| 程序 / Program | 最慢中位数 / Worst median (s) | 时限 / Limit (s) | 结果 / Result |
|---|---|---|---|
| Quotient DP + ordered meet-in-the-middle | 0.898646 | 2 | Pass; 149.54 MiB peak |
| Comparison sorting | 2.932093 | 2 | Exceeds limit on file 08 |
| Per-state binary search | 2.626888 | 2 | Exceeds limit on file 09 |
时限按标程最慢中位数乘 2，并向上取整至 0.5 秒。标程通过余量为 2.226 倍，较快的慢程序用时为时限的 1.313×，达到本题 1.3 的分离目标。三种实现共用剪枝、前缀权重和批量模运算，区别主要为建表或查询算法。有限测试不覆盖同阶算法的所有实现，目标 OJ 需重新校准。
The limit doubles the reference median and rounds upward to 0.5 seconds. The passing margin is 2.226×; the closer slow witness takes 1.313× the limit, meeting the chosen 1.3 separation target. All three programs share pruning, prefix weights, and batched modular arithmetic. These measurements do not cover every implementation with the same asymptotic bound; recalibrate on the target judge.