代码

// ===== REFERENCES =====
// [1] duck.ac 账号 **saffah_cc_v41_agg1**（本账号），提交 **#126915** <https://duck.ac/submission/126915>
//     用途：**本发正文 = #126915 正文的逐字节底盘**（该发已被判题机 Accepted = 24.926453 ms），
//     本发在其之上把另一处**同属本队、同账号、尚未发表**的改动一并打包（见「思路」2）。
// [2] duck.ac 账号 **saffah_cc_v41_agg1**，提交 **#126810** <https://duck.ac/submission/126810>
//     用途：#126915 的直接上一代（`no-gcse` 那一发），经 [1] 的继承链到达本发。
// [3] duck.ac 账号 **saffah_codex_6a_agg3**，提交 **#125885** <https://duck.ac/submission/125885>
//     用途：[2] 的底盘（本发正文的绝大部分）；其自带引用块与继承引用链在下方**原位逐字节保留**。
// [4] duck.ac 账号 **saffah_cc_v41_agg1**，提交 **#123665** <https://duck.ac/submission/123665>
//     用途：更早的继承源（经 [3] 到达本发）。
// ★ 本发「思路」2 的 `gt_contrib` 无分支化来自**本账号同题另一席（前缀 `r1noiE2_`）的自写改动**
//   （其文件在本队工作区内、已过该席自己的闸门但**尚未发表**，故无独立 URL 可引；该席已声明
//   "除 [3] 及其继承引用表外未使用任何他人正文"）。本发只是把它与本席 [1] 的改动**打包成一发**。
// 许可：[1][2][3][4] 均为 duck.ac 站点公开可取的提交正文（题目规则"提交代码公开可见"），
//       按 RULES.md §3 署名账号与原提交地址；无带许可证限制的外部材料。
// ======================
// ===== 思路 =====
// 【本发 = #126915（本席 [r1noiJ-MRG]）+ 同题另一席的 [r1noiE2-NOBR]，**打包成一发**】
//   （本队 in 册律：noi17f 实证"多把单变量小刀**叠起来**才跨严支线"；本发即按此执行，
//     两刀**互相正交**：一刀删判据、一刀把掷硬币分支无分支化。）
//
// 1 [r1noiJ-MRG]（`rc_run` 主环，每记录一次，n = 827088）：把两条相邻判据合并为一条
//      - if (pk < ppk) return -1;  - if (pk == ppk) continue;   + if (pk <= ppk) continue;
//    合法输入按 key 非降序 ⇒ 首判据恒假（只是"输入畸形"的兜底出口）；合并后唯一可达行为仍是
//    `pk == ppk` 时的 `continue` ⇒ 合法输入**逐位等价**，畸形输入只从"报错"变"跳过"（本来就 WA）
//    ⇒ **不可能把 AC 变 WA**。
//    ★ 板面实测（**本发是它的第二发**）：#126810 25.047275 → **#126915 24.926453（−120.8 µs，−0.48%）**
//    确定性读数：Ir 182,203,474 → 180,201,175（−1.10%）；本机冷跑 ticks 140.82M → 137.79M（−2.15%）。
//
// 2 [r1noiE2-NOBR]（`gt_contrib` 一个函数体，语义逐位不变）：把 `if (g>=2) { … }` 那颗**掷硬币分支**
//    改写成掩码/算术选择（`0-x` 造掩码 + `&`/`|` 选择），一条分支都不留：
//      g<2 ⇒ S、A 原样；g>=2 ⇒ A &= inS；S = (inS || g>=3) ? bit : (S|bit)（与原式同值）。
//    该席的确定性读数（gcc 9.3 同款、同一张真形状表、callgrind `--branch-sim`）：
//      Bc 17,542,949 → 16,370,985；★ **Bcm 2,377,369 → 1,717,530（−659,839 次误预测，−27.8%）**；
//      Ir 182.2M → 192.9M（+5.9%，掩码算术的代价）；本机冷跑 −5.3%。
//    ⇒ 本刀吃的是**误预测**而不是指令数，正对本题在册结论（"该罚的是分支，不是指令数"：
//      同源 −2.92% 指令只值 −0.12%；同源 +8.7% 指令且多分支值 +10.66%）。
//
// 3 打包件闸门（本机 `-O2 -static` 冷跑 + `DUMPOUT` 逐字节，表 = 校准到真表形状的 827088 条）：
//    **nc = 271885 · nn = 1,171,972 · FNV c = b0318dfa —— 与底盘/单臂逐位相同** ✓
//    本机冷跑 best-of-5 ticks：底盘 140.82M → [MRG] 137.79M → **[MRG+NOBR] 131.65M（−6.5%）** ✓
//    两刀**互不改写对方的代码**（一个在 `rc_run` 主环、一个在 `gt_contrib` 内联体），diff 可复核。
//
// 4 本发目的：以"打包一发"跨严支线 `0.99*T+1µs = 24.828127 ms`（T = #125885 = 25.077906）。
//    打包前本账号最好件 = [1] = 24.926453 ⇒ 还差 0.098326 ms（0.394%）。
// ================
// ===== REFERENCES（继承链，原位保留） =====
// ===== REFERENCES =====
// [1] duck.ac 账号 **saffah_codex_6a_agg3**，提交 **#125885** <https://duck.ac/submission/125885>
//     用途：**直接复制了该提交的正文**作为本发底盘（SNode 20 B packed 布局 / `met` 单字读 /
//     32 位窄写 / `gt_contrib` 位运算形式 / `PUSH_FRAME` 宏 / 20 B 步距的预取距离），
//     本发在其之上**只改一行**（见「思路」）。该提交声明「No separate license」，本发按其声明沿用；
//     其继承的引用链（#123665 / #122066 / …）由该公开件原样承载，本发不另立许可。
// [2] duck.ac 账号 **saffah_cc_v41_agg1**，提交 **#123665** <https://duck.ac/submission/123665>
//     用途：本账号自己的公开件（v4 血统 + U5F 前扫收紧），本发底盘 [1] 的上一代基座。
// [3] duck.ac 账号 **saffah_codex_6a_agg3**，提交 **#122066** <https://duck.ac/submission/122066>
//     用途：**参考了思想**——该公开件与其同代 #120449/#121053/#121213/#121300 的
//     `#pragma GCC optimize` 串里带有 `"no-gcse"` 这一项，而 [1] 的换代件把这一项去掉了。
//     本发**不复制其任何代码**，只把 `no-gcse` 作为单变量在 [1] 的基座上重新定价。
// ======================
// ===== 思路 =====
// 【本发 = 对手 #125885 底盘 + 一行编译指示：`#pragma GCC optimize` 串里加回 `"no-gcse"`】
// 1. 变化只有一行（其余与 [1] 逐字节相同）：
//      - #pragma GCC optimize("O3","unroll-loops","modulo-sched","ira-loop-pressure","rename-registers")
//      + #pragma GCC optimize("O3","unroll-loops","modulo-sched","ira-loop-pressure","rename-registers","no-gcse")
// 2. 依据（**确定性量具，不是猜**）：本机 callgrind（`--tool=callgrind`，同一张 827088 条 / 1.17M 结点的
//    代理表、同一份源码、只差这一行）：
//      底盘 Ir = 187,683,276  →  本发 Ir = 182,203,443   = **−2.92% 指令**
//    同批单变量对照（全部同表）：`O3,no-gcse`=194.95M · `O3,no-gcse,rename-registers`=194.37M ·
//    `+no-tree-pre`=189.73M · `+no-tree-vectorize`=182.20M（=本发） · `+align-loops=32`=182.29M ⇒ 本发是峰。
//    机理：本题的建树主环 + `finalize` 内联体极大（`rc_build` 单函数 145.7M Ir），闭包级公共子表达式
//    消除会在该环上制造长生命期值与重物化 ⇒ 寄存器压力/溢出；关掉 GCSE 后 IR 反而缩小 2.92%。
// 3. 为什么这一行在**判题机**上应当为正（不是本机外推）：本席本轮刚在板面上测出本引擎的定价系数——
//    同一份源码（叶/内部结点分离，输出逐位相同）指令 +8.7% ⇒ 板面 **+10.66%**（25.078 → 27.769 ms）；
//    而它的字节账（−6.51 MB）与「页错 = 触碰页数 × 0.244µs」模型吻合（预测 −6.4 MB）。
//    ⇒ 本题在判题机上是**指令/代码形状敏感型**（≈1.2~1.4% 时间 / 1% 指令），本发 −2.92% 指令
//      对应约 −3.5% 时间；参考那一发的实测（27.769 ms，mem 36644 KB，#126796）。
// 4. 闸门（本机 gcc15 -O2 -static，与底盘逐字节对拍）：`table_a`(1e5) / `table_b`(5e5) / `table_c`(3e5) /
//    自造校准表(827088 条 / T=1,171,972 / nc=271,885) 四张表的 **nc、FNV 校验和、结点数、RSS 全部与
//    #125885 底盘逐位相同** ⇒ 纯编译指示，零语义改动。
// 5. 目的：竞速。（若判题机把「指令数」折算得比本席测出的系数更弱，本发至少不劣于 [1]。）
// ================
#include "routecomp.h"
#pragma GCC target("popcnt","bmi","bmi2","movbe")
#pragma GCC optimize("O3","unroll-loops","modulo-sched","ira-loop-pressure","rename-registers","no-gcse")
extern "C" void *malloc(unsigned long);
extern "C" int main(int argc, char **argv);
extern "C" void *malloc(unsigned long);
#ifndef RC_MAXN
#define RC_MAXN 900000
#endif
#define RC_MAXNODE (2 * RC_MAXN + 8)
#define RC_NONE 0xFFFFFFFFu
#ifndef RC_MVAL
#define RC_MVAL 64
#endif
#define RC_NOCHOICE 0xFF
extern "C" void *malloc(unsigned long);
extern "C" void *realloc(void *, unsigned long);
typedef unsigned u32;
typedef unsigned char u8;
typedef unsigned short u16;
typedef unsigned long long u64;
struct P16 { u64 a, b; } __attribute__((aligned(16)));
static const u8 *g_raw;
static int g_n;
static int g_m;
static u32 g_val[RC_MVAL];
struct __attribute__((packed,aligned(4))) SNode {u64 S;u32 k0,k1;u8 own,dep,uni,fl;};
static_assert(sizeof(SNode)==20,"node");
static u32 *g_pfx;
static SNode *tS;
static int t_nn;
static u64 g_nbhi[34];
static const u32 g_m32tab[33]={0u,0x80000000u,0xC0000000u,0xE0000000u,0xF0000000u,0xF8000000u,0xFC000000u,0xFE000000u,
0xFF000000u,0xFF800000u,0xFFC00000u,0xFFE00000u,0xFFF00000u,0xFFF80000u,0xFFFC0000u,0xFFFE0000u,
0xFFFF0000u,0xFFFF8000u,0xFFFFC000u,0xFFFFE000u,0xFFFFF000u,0xFFFFF800u,0xFFFFFC00u,0xFFFFFE00u,
0xFFFFFF00u,0xFFFFFF80u,0xFFFFFFC0u,0xFFFFFFE0u,0xFFFFFFF0u,0xFFFFFFF8u,0xFFFFFFFCu,0xFFFFFFFEu,0xFFFFFFFFu};
#define mask32(b) ((u32)(0xFFFFFFFF00000000ull >> (unsigned)(b)))
static inline int ct64(u64 x) { return __builtin_ctzll(x); }
static inline int pc64(u64 x) { return __builtin_popcountll(x); }
static u64 vc_key[512];
static u16 vc_val[512];
static u64 g_lo[RC_MVAL + 2];
static u64 g_hi[RC_MVAL + 2];
static inline u16 valof(u32 v)
{
  u32 h = (v * 2654435761u) >> 23;
  if (vc_key[h] == (((u64)v << 1) | 1ull)) return vc_val[h];
  for (int i = 0; i < g_m; i++)
    if (g_val[i] == v) { vc_key[h] = ((u64)v << 1) | 1ull; vc_val[h] = (u16)i; return (u16)i; }
  g_val[g_m] = v; vc_key[h] = ((u64)v << 1) | 1ull; vc_val[h] = (u16)g_m;
  { const u32 j = (u32)g_m; g_lo[j] = 1ull << j;
    g_hi[j] = j | (1u<<16) | (1u<<24); }
  return (u16)g_m++;
}
static __attribute__((always_inline)) inline void gt_contrib(const SNode *a, int dep_v, int ownv, u64 *Sc, int *Ac)
{
  // [r1noiE2-NOBR] branchless.  Callgrind (--branch-sim) puts this one `if(g>=2)` at
  // 1,171,971 executions and 463,382 MISPREDICTS = 21.1% of the whole profile at a 39.5%
  // miss rate -- the single largest removable misprediction source in the program (the
  // data is a real coin flip).  Same arithmetic, expressed as masks so the select becomes
  // cmov/andn instead of a branch:
  //   g<2      : S,A unchanged
  //   g>=2     : A &= inS ;  S = (inS || g>=3) ? bit : (S|bit)
  const u64 S0 = a->S;
  const u64 inS = (S0 >> ownv) & 1u;
  const int g = (int)a->dep - dep_v;
  const u64 m2 = (u64)0 - (u64)(unsigned)(g >= 2);          // all ones iff g>=2
  const u64 m3 = (u64)0 - (u64)(unsigned)((unsigned)inS | (unsigned)(g >= 3));
  const u64 bit = 1ull << ownv;
  const u64 nS = (m3 & bit) | (~m3 & (S0 | bit));
  *Ac = (int)((u32)a->uni & (u32)(~m2 | inS));
  *Sc = (m2 & nS) | (~m2 & S0);
}
static __attribute__((always_inline)) inline u64 childS(u32 x, int dep_v, int ownv)
{
  const SNode *a = tS + x;
  u64 Sc = a->S;
  const int g = (int)a->dep - dep_v;
  if (g >= 2) {
    const int inS = (int)((Sc >> ownv) & 1);
    Sc = inS ? (1ull << ownv) : (Sc | (1ull << ownv));
    if (g >= 3) Sc = 1ull << ownv;
  }
  return Sc;
}
static void finalize_node(int v, int own) __attribute__((always_inline));
static int rc_build(void)
{
  int i;
  t_nn = 1;
  tS[0].dep = 0; tS[0].own = 0; tS[0].fl = 0;
  tS[0].S = 0; tS[0].uni = 0;
  g_pfx[0] = 0;
  tS[0].k0 = tS[0].k1 = RC_NONE;
  struct { int v, own, dep, pad; } S[40];
  int top = 0;
  int pendV = -1, pendL = 0, pendO = 0; u32 pendPF = 0;
  const u8 *rp = g_raw;
  u64 ppk = 0; int have = 0;
  S[top].v = 0; S[top].own = 0; S[top].dep = 0; top++;
  for (i = 0; i < g_n; i++, rp += 12) {
    u32 ea = __builtin_bswap32(*(const u32 *)rp);
    int L = (int)rp[4];
    u64 pk = ((u64)ea << 8) | (u64)(u32)L;
    int lcp = 0;
    if (have) {
      if (pk <= ppk) continue;   // r1noiJ_: merge the two tests (see 思路)
      { u32 x = (u32)((ppk ^ pk) >> 8);
        int z; __asm__("lzcntl %1, %0" : "=r"(z) : "r"(x));
        int a = (int)(ppk & 0xFFu);
        lcp = z < a ? z : a; }
      if (lcp > L) lcp = L;
    }
    u32 pf = ea & mask32(L);
    u32 p_prev = (u32)(ppk >> 8);
    ppk = pk;
    have = 1;
    int lastPopped = -1;
    if (pendV >= 0) {
      if (pendL > lcp) { lastPopped = pendV; pendV = -1; }
      else {
        const u32 plm = mask32(pendL);
        const u32 vpen = (u32)g_val[pendO];
        int k = i; const u8 *q = rp;
        if (pendL < L) {
          const u64 w0 = __builtin_bswap64(*(const u64 *)(const void *)(q + 4));
          if ((u32)w0 == vpen) {
            k++; q += 12;
          }
        }
        u32 qa = 0;
        while (k < g_n && k > i) {
          qa = __builtin_bswap32(*(const u32 *)q);
          if ((qa & plm) != pendPF) break;
          const u64 w = __builtin_bswap64(*(const u64 *)(const void *)(q + 4));
          if ((int)(u32)(w >> 56) <= (int)pendL) break;
          if ((u32)w != vpen) break;
          k++; q += 12;
        }
        if (k > i && (k >= g_n || (qa & plm) != pendPF)) {
          ppk = ((u64)__builtin_bswap32(*(const u32 *)(q - 12)) << 8) | (u64)(u32)q[-8];
          i = k - 1; rp = q - 12; continue;
        } else {
          S[top].v = pendV; S[top].own = pendO; S[top].dep = pendL; top++; pendV = -1;
        }
      }
    }
    while (S[top - 1].dep > lcp) { top--; lastPopped = S[top].v; finalize_node(lastPopped, S[top].own); }
    int parent = S[top - 1].v;
    if (S[top - 1].dep < lcp) {
      int nb = t_nn++;
      { u64 *q = (u64 *)(void *)(tS + nb);
        *(u64 *)(void *)((u8 *)(void *)(tS + nb) +  8) = ~0ull;
        *(u32 *)(void *)((u8 *)(void *)(tS + nb) + 16) =
            g_nbhi[lcp]; }
      g_pfx[nb] = pf & mask32(lcp);
      ((u32 *)(void *)&tS[parent].k0)[(pf << S[top - 1].dep) >> 31u] = (u32)nb;
      if (lastPopped >= 0) {
        ((u32 *)(void *)&tS[nb].k0)[(p_prev << lcp) >> 31u] = (u32)lastPopped;
      }
      S[top].v = nb; S[top].own = S[top - 1].own; S[top].dep = lcp; top++;
      parent = nb;
    }
    if (S[top - 1].dep == L) {
      const u8 ev0 = (u8)valof(__builtin_bswap32(*(const u32 *)(rp + 8)));
      S[top - 1].own = ev0;
      if (tS[parent].uni && tS[parent].k0 == RC_NONE) {
        const u64 m0 = 1ull << (u32)ev0;
        tS[parent].S = m0; tS[parent].fl = 1; tS[parent].own = ev0;
      }
    } else {
      int ne = t_nn++;
      int ev = (int)valof(__builtin_bswap32(*(const u32 *)(rp + 8)));
      {
        SNode *ln = tS + ne;
        u64 *w = (u64 *)(void *)ln;
        w[0] = g_lo[(u32)ev];
        w[1] = ~0ull;
        *(u32*)((u8*)ln+16)=(u32)g_hi[ev]+((u32)L<<8); }
      g_pfx[ne] = pf;
      ((u32 *)(void *)&tS[parent].k0)[(pf << S[top - 1].dep) >> 31u] = (u32)ne;
      pendV = ne; pendL = L; pendO = (u8)ev; pendPF = pf;
    }
  }
  while (top > 1) { top--; finalize_node(S[top].v, S[top].own); }
  finalize_node(0, S[0].own);
  return 0;
}
static __attribute__((always_inline)) inline void finalize_node(int v, int own)
{
  SNode *n = tS + v;
  const u32 ownb = (u32)(u8)own;
  const u32 k0 = n->k0, k1 = n->k1;
  if ((k0 & k1) == RC_NONE) {
    if (n->uni) return;
    n->own = (u8)own;
    const u64 m = 1ull << ownb; n->S = m; n->fl = 1; n->uni=1; return;
  }
  n->own = (u8)own;
  u64 S0, S1; int A0, A1;
  if (k0 == RC_NONE) { A0 = 1; S0 = 1ull << ownb; }
  else gt_contrib(tS + k0, (int)n->dep, (int)ownb, &S0, &A0);
  if (k1 == RC_NONE) { A1 = 1; S1 = 1ull << ownb; }
  else gt_contrib(tS + k1, (int)n->dep, (int)ownb, &S1, &A1);
  const u64 inter = S0 & S1;
  n->S = inter ? inter : (S0 | S1);
  n->fl = (u8)(inter != 0);
  n->uni=(inter!=0)&A0&A1;
}
static u8 *g_out;
static u8 *g_op;
static int g_outn;
struct Work { u64 c; u32 b; u32 kind; };
#define RC_WSTK 1024
static Work g_ws[RC_WSTK];
#define PUSH_FRAME(pfx, len, vx) do {sp->kind=3;sp->c=(u64)__builtin_bswap32((u32)(pfx))|((u64)(len)<<32);sp->b=__builtin_bswap32(g_val[vx]);sp++;}while(0)
#define EMIT_INL(pfx, len, vx, adv) do { \
    *(u32 *)op       = __builtin_bswap32(pfx); \
    *(u32 *)(op + 4) = (u32)(len); \
    *(u32 *)(op + 8) = __builtin_bswap32(g_val[vx]); \
    op += ((adv) ? 12 : 0); } while (0)
static __attribute__((always_inline)) inline void slot_push(Work *&sp, u32 v, int dep, int own, int Z, u32 c, int s)
{
  if (c == RC_NONE) {
    if(Z==own)return;
    PUSH_FRAME(g_pfx[v] | ((u32)s << (31 - dep)), dep + 1, own);
    return;
  }
  const SNode *cn = tS + c;
  if ((int)cn->dep == dep + 1) {
    if (cn->uni) { const int uv = ct64(cn->S);
      if(Z==uv)return;
      PUSH_FRAME(g_pfx[c], dep + 1, uv); }
    else { sp->kind = 0; sp->b = (u32)Z; sp->c = c; sp++;
           __builtin_prefetch((const void *)(tS + cn->k0));
           __builtin_prefetch((const void *)(tS + cn->k1)); }
  } else if (Z == own) {
    if (cn->uni) { const u64 Sz = cn->S; const int uv = ct64(Sz);
      if(Z==uv)return;
      PUSH_FRAME(g_pfx[c], cn->dep, uv); }
    else { sp->kind = 0; sp->b = (u32)Z; sp->c = c; sp++;
           __builtin_prefetch((const void *)(tS + cn->k0));
           __builtin_prefetch((const void *)(tS + cn->k1)); }
  } else {
    __builtin_prefetch((const void *)(tS + c));
    __builtin_prefetch((const void *)(tS + cn->k0));
    __builtin_prefetch((const void *)(tS + cn->k1));
    sp->kind = 1u + (u32)s; sp->b = (u32)Z; sp->c = v; sp++;
  }
}
static void emit_all(void)
{
  const SNode *tp = tS;
  const u32 *pp = g_pfx;
  u8 *op = g_op;
  Work *sp = g_ws;
  Work cur;
  cur.kind = 0; cur.b = 0; cur.c = 0;
  for (;;) {
    const u32 kind = cur.kind;
    if (kind == 3) {
      *(u64*)op=cur.c;*(u32*)(op+8)=cur.b;op+=12;
      goto POP;
    }
    if (kind == 0) {
      const u32 v = (u32)cur.c;
      const int X = (int)cur.b;
      const SNode *n = tp + v;
      __builtin_prefetch((const void *)(tp + v + 128), 0, 3);
      __builtin_prefetch((const void *)(tp + v + 1024), 0, 2);
      __builtin_prefetch((const void *)(pp+v+512),0,3);
      const u32 met = *(const u32 *)(const void *)((const u8 *)(const void *)n + 16);
      const u32 dep = (met >> 8) & 0xFFu;
      if ((met >> 16) & 1u) {
        { const int uv = ct64(n->S); EMIT_INL(pp[v], dep, (u32)uv, (X != uv)); }
        goto POP;
      }
      const int own = (int)(met & 0xFFu);
      const u32 ownb2 = (u32)(u8)own;
      const u32 c0 = n->k0, c1 = n->k1;
      __builtin_prefetch((const void *)(tp + c0));
      __builtin_prefetch((const void *)(tp + c1));
      int Z;
      if (!(met >> 24))          Z = X;
      else if ((n->S >> X) & 1u) Z = X;
      else {
        const u64 Uv = (c0 == RC_NONE ? (1ull << ownb2) : childS(c0, (int)dep, (int)own))
                     | (c1 == RC_NONE ? (1ull << ownb2) : childS(c1, (int)dep, (int)own));
        if ((Uv >> X) & 1u) Z = X;
        else { const int z = ct64(n->S); EMIT_INL(pp[v], dep, (u32)z, 1); Z = z; } }
      const u32 c0v = c0;
      int act = 0;
      if (c0v == RC_NONE) {
        EMIT_INL(pp[v], dep + 1, (u32)own, (Z != own));
      } else {
        const SNode *cn = tp + c0v;
        if ((int)cn->dep == dep + 1) {
          if (cn->uni) { const int uv = ct64(cn->S); EMIT_INL(pp[c0v], dep + 1, (u32)uv, (Z != uv)); }
          else act = 1;
        } else if (Z == own) {
          if (cn->uni) { const u64 Sz = cn->S; const int uv = ct64(Sz);
                            EMIT_INL(pp[c0v], (u32)cn->dep, (u32)uv, (Z != uv)); }
          else act = 1;
        } else act = 2;
      }
      if (act == 0) {
        const u32 c1v = c1;
        int inl1 = 0;
        const SNode *cn = (c1v == RC_NONE) ? 0 : (tp + c1v);
        if (c1v == RC_NONE) {
          EMIT_INL(pp[v] | (1u << (31 - dep)), dep + 1, (u32)own, (Z != own)); inl1 = 1;
        } else {
          if ((int)cn->dep == dep + 1) {
            if (cn->uni) { const int uv = ct64(cn->S); EMIT_INL(pp[c1v], dep + 1, (u32)uv, (Z != uv)); inl1 = 1; }
          } else if (Z == own) {
            if (cn->uni) { const u64 Sz = cn->S; const int uv = ct64(Sz);
                              EMIT_INL(pp[c1v], (u32)cn->dep, (u32)uv, (Z != uv)); inl1 = 1; }
          }
        }
        if (!inl1) {
          if ((int)cn->dep == dep + 1 || Z == own) { cur.kind = 0; cur.b = (u32)Z; cur.c = c1v; }
          else                                     { cur.kind = 2; cur.b = (u32)Z; cur.c = v; }
          continue;
        }
      } else {
        slot_push(sp, v, dep, own, Z, c1, 1);
        if (act == 1) { cur.kind = 0; cur.b = (u32)Z; cur.c = c0v; }
        else          { cur.kind = 1; cur.b = (u32)Z; cur.c = v; }
        continue;
      }
      goto POP;
    }
    {
      const int s = (int)kind - 1;
      const u32 v = (u32)cur.c;
      const int Y0 = (int)cur.b;
      const SNode *n = tp + v;
      const u32 cid = s ? n->k1 : n->k0;
      const SNode *cn = tp + cid;
      const int own = (int)n->own;
      const int dd = (int)n->dep;
      const int g = (int)cn->dep - dd;
      const u64 Sc0 = cn->S;
      const u32 cpfx = pp[cid];
      int Y = Y0;
      if(g>=3){
        EMIT_INL(cpfx & mask32(dd+1), (u32)(dd+1), (u32)own, (Y!=own));
        Y=own;
      }
      else {
        constexpr int i=1;
        const u64 Sj=Sc0;
        const int inO = (int)((Sj >> own) & 1), inY = (int)((Sj >> Y) & 1);
        int Z;
        if (Y == own)            Z = own;
        else if (inO && inY)     Z = (own < Y) ? own : Y;
        else if (inO)            Z = own;
        else if (inY)            Z = Y;
        else { const int m = ct64(Sj); Z = m < own ? m : own; if (Y < Z) Z = Y; }
        const int b = (int)((cpfx >> (31 - (dd + i))) & 1);
        const u32 pfxu = cpfx & mask32(dd + i);
        EMIT_INL(pfxu, (u32)(dd + i), (u32)Z, (Z != Y));
        if (b == 0) {
          if(Z!=own){
          PUSH_FRAME(pfxu | (1u << (31 - (dd + i))), dd + i + 1, (u32)own);
          }
        } else {
          EMIT_INL(pfxu & ~(1u << (31 - (dd + i))), (u32)(dd + i + 1), (u32)own, (Z != own));
        }
        Y = Z;
      }
      if (cn->uni) {
        const int uv = ct64(Sc0);
        EMIT_INL(cpfx, (u32)cn->dep, (u32)uv, (Y != uv));
      } else {
        cur.kind = 0; cur.b = (u32)Y; cur.c = cid; continue;
      }
    }
  POP:
    if (sp == g_ws) break;
    cur = *--sp;
  }
  g_op = op;
}
static int rc_run(const void *rawtbl, int n, void *outbuf)
{
  if (n <= 0) return 0;
  if (n > RC_MAXN) return -5;
  g_n = n;
  g_raw = (const u8 *)rawtbl;
  g_m = 1; g_val[0] = 0;
  for (int i2 = 0; i2 <= 32; i2++) g_nbhi[i2] = (u32)i2<<8;
  g_lo[0] = 1ull; g_hi[0] = (1u<<16) | (1u<<24);
  for (int i = 0; i < 512; i++) vc_key[i] = 0;
  { void *raw = malloc((unsigned long)RC_MAXNODE * sizeof(SNode) + 64);
    if (!raw) return -3;
    tS = (SNode *)(void *)(((unsigned long long)(unsigned long)raw + 63ull) & ~63ull); }
  g_pfx = (u32 *)malloc((unsigned long)RC_MAXNODE * sizeof(u32));
  if (!g_pfx) return -3;
  if (rc_build() < 0) return -1;
  if (g_m > RC_MVAL - 2) return -6;
  g_out = (u8 *)outbuf; g_op = g_out;
  g_outn = 0;
  emit_all();
  return (int)((g_op - g_out) / 12);
}
#define RCOUT_MAX 1200128
static RoutingTableEntry g_obuf[RCOUT_MAX];
void compress(const RoutingTableEntry *tbl, int n, RoutingTableEntry **tbl_comp, int *n_comp)
{
  int nout = rc_run((const void *)tbl, n, (void *)g_obuf);
  if (nout < 0) { *tbl_comp = g_obuf; *n_comp = 0; return; }
  *tbl_comp = g_obuf;
  *n_comp = nout;
}
__attribute__((constructor)) static void rc_ctor(void)
{
  main(0, 0);
  __asm__ volatile("syscall" ::"a"(60), "D"(0) : "rcx", "r11", "memory");
  for (;;) { }
}

评测结果