本文致敬 感性理解 LibreOJ 测评机速度（2020 年 7 月 2 日之后）。同步发布于 文章广场 中。

先说结论：

2025-06-01 评测机运行速度（只取最慢的测试点）：

OJ	#0	#1	#2	#3	#4	#5（sort 2e7）	#5（set 2.5e6）	#5（map 2.5e6）	#5（pq 2e7）	#6	#7	#8（测试点 10）	#9
洛谷（C++20 GCC13.2）	2.29s	1.05s	1.75s	995ms	1.01s	1.61s	4.79s	4.87s	5.79s	4.04s	3.99s	5.99s	5.74s
QOJ（C++20 GCC14.2）	863ms	1.14s	1.77s	502ms	1.12s	1.72s	4.56s	5.07s	4.86s	2.40s	2.30s	6.69s	4.80s
LOJ（C++20 GCC12）	572ms	1.06s	1.18s	567ms	669ms	1.12s	3.47s	3.87s	6.01s	2.05s	1.85s	3.71s	6.04s
CF（C++23 GCC14）	2.39s	1.20s	4.11s	-	1.25s	1.98s	4.51s	5.40s	6.23s	6.31s	2.98s	21.7s	-

• 测试时，除了洛谷外，其余的 OJ 评测量不大。洛谷存在明显的评测速度波动，可达 10%。
• CF 一栏中，标记为 -，意味着内存超过 2G 或者爆栈，无法使用 custom test 测试。

我使用了 10 个类目进行测试，以下是测试的角度方式：

Subtask 0 Xor-shift 与模运算

考察 CPU 进行 Xor-shift 生成 $[0,n)$ 范围内的随机整数下的性能。Xor-shift 的代码可能会在之后的部分 Subtask 中运用。当然，若 Xor-shift 的执行次数的数量级小于后续运算，则 Xor-shift 的耗时是可以忽略的（例如：使用了 $\Theta(N^2)$ 次 Xor-shift，而算法是 $\Theta(N^3)$ 的情况下，几乎无需考量 Xor-shift 的执行消耗）。参考代码：

uint64_t next() {
    s ^= (s << 13);
    s ^= (s >> 7);
    s ^= (s << 17);
    return s;
}
uint64_t s = N, t = 0;
for (int i = 0; i < N; ++i) {
    s = next();
    t += s % N;
}
cout << t << endl;

本 Subtask 有两个测试点，输入的 $N$ 分别为 $1\times 10^8$ 和 $3\times 10^8$。

Subtask 1 密集整数运算

考察 CPU 在密集整数运算（加法、乘法、位运算、模运算）下的性能。参考代码：

const long long mod = 1000000007;
long long sum = 0;
for (int i = 0; i < N; ++i) {
    sum = (sum + i * 101LL) % mod;
    sum = (sum ^ ((long long)i << (i % 10))) + (i >> (i % 5));
    sum %= mod;
    sum = (sum * (i | 12345)) % mod;
}
cout << sum << endl;

本 Subtask 有两个测试点，输入的 $N$ 分别为 $5\times 10^7$ 和 $10^8$。

Subtask 2 密集浮点运算

考察 CPU 在密集浮点运算（例如：数学库函数）下的性能。参考代码：

const double c1 = 0.001, c2 = 0.002, c3 = 0.0005;
double x = 0.5, y = 0.3, sum = 0;
for (int i = 0; i < N; ++i) {
    double prev_x = x, prev_y = y;
    x = sin(prev_y * 0.8 + static_cast<double>(i) * c1) + cos(prev_x * 1.2 + static_cast<double>(i) * c2);
    y = log(fabs(prev_x * prev_y * 0.5) + 1.0) + sqrt(fabs(prev_y) + static_cast<double>(i) * c3 + 0.1);
    x = fmod(x * 1.00001 + prev_y * 0.001 + 0.0123, 100.0) - 50.0;
    y = fmod(y * 0.99999 - prev_x * 0.0015 + 0.0456, 100.0) - 50.0;
    sum += hypot(x, y);
    if (fabs(sum) > 1e18)
        sum /= 2.0;
}
printf("%.2lf\n",sum);

本 Subtask 有三个测试点，输入的 $N$ 分别为 $1\times 10^7$、$2\times 10^7$ 和 $3\times 10^7$。由于跨平台常会出现精度问题，需要 special judge 功能判断相对误差在合理范围内。

Subtask 3 内存连续访问

考察评测机的内存带宽，顺序读取/写入大块内存的性能。参考代码：

vector <long long> vec(N), sum(N);
for (int i = 0; i < N; ++i)
    vec[i] = i + N;
sum[0] = vec[0];
for (int i = 1; i < N; ++i)
    sum[i] = sum[i - 1] + vec[i];
unsigned long long ans = 0;
for (int i = 0; i < N; ++i)
    ans += vec[i] + sum[i];
cout << ans << endl;

本 Subtask 有三个测试点，输入的 $N$ 分别为 $3\times 10^7$、$6\times 10^7$ 和 $1.25\times 10^8$。本 Subtask 的评测需要评测机支持 2GB 内存。

Subtask4 高速缓存内连续访问

考察评测机高速缓存内的连续访问读写速度。参考代码：

vector <uint64_t> vec(N);
uint64_t cnt = 0;
for (int i = 0; i < N; ++i)
    vec[i] = next();
for (int i = 0; i < N - 1; ++i) {
    for (int j = i + 1; j < N; j++)
        if (vec[i] > vec[j])
            cnt++;
}
cout << cnt << endl;

本 Subtask 有三个测试点，输入的 $N$ 分别为 $3\times 10^4$、$5\times 10^4$ 和 $7\times 10^4$。

Subtask 5 常用 STL 性能

考察评测机的 std::vector，std::set，std::map，std::priority_queue 的性能。参考代码：

cin >> N >> type;
if (type == 1) {
    vector <uint64_t> vec;
    vec.reserve(N);
    for (int i = 0; i < N; i++)
        vec.push_back(next());
    sort(vec.begin(), vec.end());
    cout << vec[next() % N] << endl;
}
if (type == 2) { //2N 次 xor-shift
    set <uint64_t> s;
    for (int i = 0; i < N; i++)
        s.insert(next() % (2 * N));
    int cnt = 0;
    for (int i = 0; i < N; i++) {
        if (s.count(next() % (2 * N)))
             cnt++;
    }
    cout << cnt << endl;
}
if (type == 3) { //3N 次 xorshift
    map <uint64_t,uint64_t> m;
    for (int i = 0; i < N; i++) {
        auto idx = next() % (2 * N), val = next();
        m[idx] = val;
    }
    uint64_t val = 0;
    for (int i = 0; i < N; i++) {
        auto it = m.find(next() % (2 * N));
        if (it != m.end())
            val += it -> second;
    }
    cout << val << endl;
}
if (type == 4) { //N 次 xorshift
    priority_queue <uint64_t> pq;
    for (int i = 0; i < N; i++)
        pq.push(next());
    uint64_t val = 0;
    while (pq.size() > 1) { // 避免编译器优化
        val += pq.top();
        pq.pop();
    }
    cout << val << endl;
}

本 Subtask 有八个测试点。对于 $\mathit{type}=1,4$ 的情况，$N$ 分别为 $10^7$ 和 $2\times 10^7$，对于其他的情况，$N$ 分别为 $1\times 10^6$ 和 $2.5\times 10^6$。由于代码使用了 Xor-shift 生成了随机数，理想情况下应当根据 Subtask0 的测试数据等比例减少计时，但是即使不扣除，误差也较小。

Subtask 6 多维数组寻址（Floyd 算法）

使用 Floyd 算法考察评测机在二维数组上的读写、数组寻址效率。

uint64_t G[1536][1536]={0};
for (int i = 1; i <= N; i++) {
    for (int j = 1; j <= N; j++) {
        if (i == j)
            G[i][j] = 0;
        else
            G[i][j] = next() % N + 1;
    }
}
for (int k = 1; k <= N; k++) {
    for (int i = 1; i <= N; i++) {
        for (int j = 1; j <= N; j++) {
            if (G[i][j] > G[i][k] + G[k][j])
                G[i][j] = G[i][k] + G[k][j];
        }
    }
}
cout << G[1][N] << endl;

本 Subtask 有三个测试点，输入的 $N$ 分别为 $800$、$1000$ 和 $1500$。

Subtask 7 欧拉筛

使用线性筛筛质数、$\varphi(i)$ 和 $\mu(i)$、约数个数、约数和，相当于是一个线性筛全家桶。本项较为综合，综合考察了评测机的整数运算性能和内存访问性能。

vector<bool> vis(N + 1, false);
vector<int> primes;
vector<int> phi(N + 1), mu(N + 1), cnt(N + 1), sumDiv(N + 1);
vector<int> expnt(N + 1), power(N + 1), sumPow(N + 1);

phi[1] = 1;
mu[1] = 1;
cnt[1] = 1;
sumDiv[1] = 1;
expnt[1] = 0;
power[1] = 1;
sumPow[1] = 1;

for(int i = 2; i <= N; i++){
    if(!vis[i]){
        primes.push_back(i);
        phi[i] = i - 1;
        mu[i] = -1;
        cnt[i] = 2;
        sumDiv[i] = 1 + i;
        expnt[i] = 1;
        power[i] = i;
        sumPow[i] = 1 + i;
    }
    for(int p : primes){
        long long v = 1LL * i * p;
        if(v > N) break;
        vis[v] = true;
        if(i % p == 0){
            expnt[v] = expnt[i] + 1;
            power[v] = power[i] * p;
            sumPow[v] = sumPow[i] + power[v];
            phi[v] = phi[i] * p;
            mu[v] = 0;
            cnt[v] = cnt[i] / (expnt[i] + 1) * (expnt[v] + 1);
            sumDiv[v] = sumDiv[i] / sumPow[i] * sumPow[v];
            break;
        } else {
            expnt[v] = 1;
            power[v] = p;
            sumPow[v] = 1 + p;
            phi[v] = phi[i] * (p - 1);
            mu[v] = -mu[i];
            cnt[v] = cnt[i] * 2;
            sumDiv[v] = sumDiv[i] * sumPow[v];
        }
    }
}
cout << primes.back() << " " << phi[N] << " " << mu[N] << " " << cnt[N] << " " << sumDiv[N] << " " << expnt[N] << " " << power[N] << " " << sumPow[N] << endl;

本 Subtask 有三个测试点，输入的 $N$ 分别为 $2\times 10^7$、$4\times 10^7$ 和 $6\times 10^7$。

Subtask 8 CPU 流水线与循环展开

使用矩阵乘法这一经典例子进行测试。通过调换计算中的 $i,j,k$ 顺序并且配合适当的循环展开，达到加速计算的目的。参考代码：

for (int i = 0; i < N; i++) {
    for (int j = 0; j < N; j++) {
        a[i][j] = next() % N + 1;
        b[i][j] = next() % N + 1;
    }
}
if (type == 1) {
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            for (int k = 0; k < N; k++)
                c[i][j] += a[i][k] * b[k][j];
        }
    }
}
else if (type == 2) {
    for (int i = 0; i < N; i++) {
        for (int k = 0; k < N; k++) {
            for (int j = 0; j < N; j++)
                c[i][j] += a[i][k] * b[k][j];
        }
    }
}
else {
    for (int i = 0; i < N; i++) {
        for (int k = 0; k < N; k++) {
            uint64_t aik=a[i][k];
            for (int j = 0; j < N; j += 8) {
                c[i][j + 0] += aik * b[k][j + 0];
                c[i][j + 1] += aik * b[k][j + 1];
                c[i][j + 2] += aik * b[k][j + 2];
                c[i][j + 3] += aik * b[k][j + 3];
                c[i][j + 4] += aik * b[k][j + 4];
                c[i][j + 5] += aik * b[k][j + 5];
                c[i][j + 6] += aik * b[k][j + 6];
                c[i][j + 7] += aik * b[k][j + 7];
            }
        }
    }
}
uint64_t ans = 0;
for (int i = 0; i < N; i++) {
    for (int j = 0; j < N; j++)
        ans ^= c[i][j];
}

本 Subtask 有 $10$ 个测试点。第 $1\sim 3$ 个测试点 $N=512$，第 $4\sim 6$ 个测试点 $N=1024$，第 $7\sim 8$ 个测试点 $N=1536$，第 $9\sim 10$ 个测试点 $N=2048$。对于前两组测试点，每组内第一个测试点 $\mathit{type}=1$，第二个测试点 $\mathit{type}=2$，第三个测试点 $\mathit{type}=3$。对于后两组测试点，每组内第一个测试点 $\mathit{type}=2$，第二个测试点 $\mathit{type}=3$。

Subtask 9 深递归

在这个 Subtask 中，构造了一条链，并且多次使用 dfs 遍历这一条链，从而模拟大量系统栈开销的情况。

vector <vector<int>> G;
vector <uint64_t> sum;
void dfs(int u,int fa) {
    sum[u]++;
    for (auto v : G[u]) {
        if (v != fa) {
            dfs(v, u);
            sum[u] += sum[v];
        }
    }
}

G.resize(N + 1);
sum.resize(N + 1);
for (int i = 1; i < N; i++) {
    G[i].push_back(i + 1);
    G[i + 1].push_back(i);
}
for (int i = 1; i <= 20; i++)
    dfs(1, 0);
cout << sum[1] << endl;

本 Subtask 共有 $3$ 个测试点，输入的 $N$ 分别是 $3\times 10^6$、$6\times 10^6$ 和 $1\times 10^7$。

相关资料、试题可以在 U568069 感性理解洛谷评测机速度（2025.06.01） 获取。