题解：CEOI 重测提交排序问题（均衡分配方案）

题目核心分析

问题本质

给定 $N$ 个处理器核心，每个核心有 $S$ 份提交（$S$ 是 $2$ 的幂），每份提交属于 $T$ 道题之一。要求对每个核心的提交列表重新排序，使得每分钟内所有核心同时测评的每道题的提交数，其最大值与最小值之差 ≤ 1（即全局分配均衡）。

关键约束

1. 每个核心的提交列表排序后，必须与原始列表的题目集合完全一致（仅顺序不同）；
2. $S = 2^k$（$k$ 为正整数），这是算法设计的核心前提；
3. 最终需满足：对任意题目 $t$，记 $cnt_j(t)$ 为第 $j$ 分钟测评 $t$ 的核心数，则 $\max(cnt_1(t), ..., cnt_S(t)) - \min(cnt_1(t), ..., cnt_S(t)) ≤ 1$。

算法思路：分治+欧拉回路的均衡排序

核心思想

利用 $S$ 是 $2$ 的幂的特性，采用分治策略：将每个核心的提交列表逐层拆分为两个长度相等的子列表，通过交换子列表元素，逐步平衡全局题目在各分钟的分布。交换决策通过欧拉回路构建，确保每一层拆分后的局部均衡，最终实现全局均衡。

分治层级划分

$S = 2^k$ 意味着可将排序过程分为 $k$ 层（从 $z = k-1$ 到 $z = 0$）：

• 第 $z$ 层对应的子列表长度为 $len = 2^z$；
• 每层将当前列表按长度 $len$ 拆分为若干对相邻子列表（例如 $S=4$ 时，$z=1$ 层拆分为长度 $2$ 的子列表对，$z=0$ 层拆分为长度 $1$ 的子列表对）。

欧拉回路的作用（子列表对交换决策）

对于每层的每个子列表对（长度均为 $len$），需决定是否交换两个子列表的位置，以平衡全局题目分布。交换决策通过构建图论模型并找欧拉回路实现：

1. 建图：
   • 节点：代表题目（$1 \sim T$）；
   • 边：对每个核心的当前子列表对（位置 $p | j$ 和 $p | j | 2^z$），连接边 $(a[i][p|j], a[i][p|j|2^z])$，边的编号为核心索引与子列表索引的组合（$id = i << z | j$）。
2. 找欧拉回路：
   • 欧拉回路的每条边对应一个交换决策：若边的方向与建图时一致，则不交换；否则交换对应子列表对。
   • 这样的设计能保证：每层处理后，每个题目在“子列表对”维度的分布均衡，为最终全局均衡奠定基础。

算法步骤总结

1. 初始化：读取输入数据，存储每个核心的原始提交列表；
2. 分治处理（共 $k = \log_2 S$ 层）：
   • 对每层 $z$，按子列表长度 $2^z$ 拆分所有核心的提交列表；
   • 为当前层的所有子列表对建图（题目为节点，子列表对为边）；
   • 寻找欧拉回路，根据回路方向决定是否交换子列表对；
3. 输出结果：所有层处理完毕后，每个核心的提交列表即为满足条件的排序方案。

代码逐段解析

1. 数据结构与工具宏

#include <cstdio>
#include <vector>
#define swap(A, B) (A ^= B ^= A ^= B)  // 异或交换（高效交换两个变量）
#define lg(x) (31 - __builtin_clz(x))  // 计算 2 的幂的指数（x=2^k 时返回 k）

const int MX = 100010, MXT = 500010;  // MX：核心数/题目数上限；MXT：总提交数上限（N*S ≤ 5e5）

// 内存池：高效存储 N 个核心的 S 份提交（避免多次动态分配）
struct mem {
    int pool[MXT], *a[MX];  // pool：连续内存池；a[i]：第 i 个核心的提交列表指针

    void init(int n, int s) {
        for (int i = 0; i < n; a[i] = pool + i * s, i++);  // 分配每个核心的列表指针
    }

    auto operator[](int i) { return a[i]; }  // 重载 []，方便访问第 i 个核心的列表
} a;

• 内存池设计：由于 $N \cdot S ≤ 5 \times 10^5$，使用连续内存池存储所有提交，避免分散动态分配的开销，提升效率；
• lg 宏：利用 __builtin_clz（统计前导零）快速计算 $S$ 的对数（如 $S=4$ 时，lg(4)=2）。

2. 图论模块（欧拉回路实现）

namespace solve {
namespace gr {
struct edge {
    int to, id;  // to：目标节点；id：边的编号（对应核心+子列表索引）
    bool fl;     // fl：边的方向标记（建图时的原始方向）
};

std::vector <edge> G[MX];  // 图的邻接表（节点为题目）
std::vector <int> vv;      // 存储所有涉及的节点（题目），用于后续遍历
int deg[MX];               // 节点的度数（用于判断欧拉回路入口）
bool vis[MXT];             // 标记边是否已访问（避免重复处理）

// 添加边：u 和 v 是题目，id 是边的唯一标识
void adde(int u, int v, int id) {
    G[u].push_back({ v, id, true });   // 正向边（u→v）
    G[v].push_back({ u, id, false });  // 反向边（v→u）
    deg[u]++; deg[v]++;               // 度数+1
    vis[id] = false;
    vv.push_back(u); vv.push_back(v);  // 记录涉及的节点
}

// 深度优先搜索找欧拉回路，f 是交换决策的回调函数
template <typename F>
void DFS(int u, const F &f) {
    // 移除已访问的边
    for (; not G[u].empty() and vis[G[u].back().id]; G[u].pop_back());

    if (not G[u].empty()) {
        auto &e = G[u].back();
        vis[e.id] = true;  // 标记边已访问

        if (not e.fl) f(e.id);  // 反向边：执行交换操作（回调函数 f）

        deg[u]--; deg[e.to]--;  // 度数更新（欧拉回路中边的度数成对消耗）
        DFS(e.to, f);           // 递归访问下一个节点
    }
}

// 处理当前层的所有边，生成交换决策
template <typename F>
void solve(const F &f) {
    // 第一步：处理奇度数节点（欧拉路径入口）
    for (int u : vv)
        if (deg[u] & 1)  // 度数为奇数的节点必须作为起点/终点
            DFS(u, f);

    // 第二步：处理剩余的偶度数节点（欧拉回路）
    for (int u : vv)
        DFS(u, f);

    // 清空数据，准备下一层处理
    for (int u : vv) G[u].clear();
    vv.clear();
}
}

• 欧拉回路适配：由于题目保证存在合法方案，建图后每个节点的度数必为偶数（或通过奇度数节点配对形成欧拉路径），确保能找到完整回路；
• 回调函数设计：将交换操作封装为回调函数，使图论模块与核心逻辑解耦，提高代码复用性。

3. 核心分治逻辑

void solve(int n, int s) {
    int k = lg(s);  // 分治层数（S=2^k）
    // 从最高层到最低层（z = k-1 到 0）
    for (int z = k - 1; ~z; z--) {
        int len = 1 << z;  // 当前层子列表长度：2^z
        // 遍历所有子列表对的起始位置 p（步长为 2*len）
        for (int p = 0; p < s; p += 2 << z) {
            // 为每个核心的当前子列表对建边
            for (int i = 0; i < n; i++) {
                for (int j = 0; j < len; j++) {
                    // 子列表对的两个位置：p|j 和 p|j|len（len=2^z）
                    int u = a[i][p | j];
                    int v = a[i][p | j | len];
                    int id = (i << z) | j;  // 边的唯一编号（核心i + 子列表j）
                    gr::adde(u, v, id);
                }
            }

            // 寻找欧拉回路，执行交换决策
            gr::solve([&](int id) {
                int i = id >> z;  // 解析核心编号（id = i*len + j）
                int j = id & (len - 1);  // 解析子列表索引
                int pos1 = p | j;  // 子列表对的第一个位置
                int pos2 = p | j | len;  // 子列表对的第二个位置
                swap(a[i][pos1], a[i][pos2]);  // 交换两个位置的元素
            });
        }
    }
}
}

• 分治层级遍历：从最高层（子列表长度 $S/2$）到最低层（子列表长度 $1$），逐层细化均衡；
• 子列表对处理：每层按步长 $2 \times len$ 遍历所有子列表对，建图后通过欧拉回路决定是否交换，确保每层处理后局部均衡。

4. 主函数（输入输出与初始化）

int main() {
    int n, s, t;
    scanf("%d%d%*d", &n, &s, &t);  // 读取 N, S, T（T 未直接使用，因建图用题目编号）
    a.init(n, s);  // 初始化内存池，分配提交列表空间

    // 读取每个核心的原始提交列表
    for (int i = 0; i < n; i++)
        for (int j = 0; j < s; scanf("%d", a[i] + j++));

    solve::solve(n, s);  // 执行分治+欧拉回路排序

    // 输出结果
    for (int i = 0; i < n; putchar('\n'), i++)
        for (int j = 0; j < s; printf("%d ", a[i][j++]));

    return 0;
}

• 输入处理：忽略 $T$（因题目编号直接作为图的节点，无需额外存储）；
• 输出：按核心顺序输出排序后的提交列表，每个核心的列表占一行。

复杂度分析

时间复杂度

• 分治层数：$k = \log_2 S$（$S ≤ 10^5$，故 $k ≤ 17$）；
• 每层处理：建图和找欧拉回路的时间与边数成正比，每层边数为 $N \times S/2$（每个核心有 $S/(2 \times len) \times len = S/2$ 条边）；
• 总时间：$O(k \times N \times S) = O(N \times S \times \log S)$，因 $N \times S ≤ 5 \times 10^5$，$\log S ≤ 17$，总操作数约 $8.5 \times 10^6$，满足时间限制。

空间复杂度

• 内存池：$O(N \times S)$（存储所有提交）；
• 图结构：每层边数为 $O(N \times S)$，但处理后立即清空，故峰值空间为 $O(N \times S)$，符合内存限制。