洛谷 P2249 【深基13.例1】查找

// P2249 查找 —— 大多数人真实的第一版：一个一个看过去
//
// 题目要的是「这个数**第一次**出现的编号」，那最直白的写法就是从左往右扫，
// 撞见的第一个相等的就是答案；扫完了没撞见就输出 -1。
//
// ★ 它是**对的** —— 「从左往右第一个」这句话本身就是答案的定义，不可能错。
//   问题只有一个字：慢。n <= 10⁶、m <= 10⁵，最坏要看 10¹¹ 次
//   （比如所有询问都问一个不存在的数，每次都得扫满一整趟）。
//   这笔账在 p2249Count.cpp 里算，也在页面那张表里。

#include <bits/stdc++.h>
using namespace std;

static int a[1000006];

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, m;
    if (!(cin >> n >> m)) return 0;
    for (int i = 1; i <= n; i++) cin >> a[i];

    for (int k = 0; k < m; k++) {
        int q;
        cin >> q;
        int ans = -1;
        for (int i = 1; i <= n; i++) {              // ← 这一层就是全部的代价
            if (a[i] == q) { ans = i; break; }
        }
        cout << ans << ' ';
    }
    cout << '\n';
    return 0;
}

// 换一把尺子：暴力和二分各要看多少个数
//
// 用法：./p2249Count <n> <m>          人话版（带秒表）
//       ./p2249Count <n> <m> csv      只打 `键,值`，给 check:viz 用
//
// ★ 为什么要数次数而不是只看秒表：这道题的暴力在满数据上**根本跑不完**，
//   秒表量不出来的东西，次数算得出来（第 3 章起就是这么干的）。
//
// 两笔账：
//   · 暴力：每次询问最坏扫满 n 个 ⇒ n × m 次比较。
//     ⚠ 「最坏」是有形状的 —— 必须是**问不存在的数**，否则平均扫到一半就 break 了。
//       所以这里同时算「最坏」和「随机命中的平均」两个数，差在 2 倍左右。
//   · 二分：每次询问 ⌊log2(n)⌋ + 1 次 ⇒ m × 那个数。
//
// 这两个数都是**真跑出来数的**（不是套公式），跑的就是 p2249Brute / p2249 里那两段循环。

#include <bits/stdc++.h>
#include <chrono>
using namespace std;
using namespace std::chrono;

static double now_ms() {
    timespec t;
    clock_gettime(CLOCK_MONOTONIC, &t);
    return t.tv_sec * 1000.0 + t.tv_nsec / 1e6;
}

static vector<int> a;                       // 1..n
static int n;
static long long steps;

static int bruteFind(int q) {               // p2249Brute.cpp 里那一层
    for (int i = 1; i <= n; i++) { steps++; if (a[i] == q) return i; }
    return -1;
}
static int binFind(int q) {                 // p2249.cpp 里那个模板
    int l = 1, r = n + 1;
    while (l < r) { steps++; int mid = l + (r - l) / 2; if (a[mid] >= q) r = mid; else l = mid + 1; }
    return (l <= n && a[l] == q) ? l : -1;
}

int main(int argc, char** argv) {
    n = (argc > 1) ? atoi(argv[1]) : 200000;
    int m = (argc > 2) ? atoi(argv[2]) : 2000;
    bool csv = (argc > 3 && string(argv[3]) == "csv");

    mt19937 rng(20260827u);
    a.assign(n + 2, 0);
    for (int i = 1; i <= n; i++) a[i] = (int)(rng() % 500000000u) * 2;       // 全偶数，且守住 <= 10⁹
    sort(a.begin() + 1, a.begin() + n + 1);

    vector<int> miss(m), hit(m);
    for (int k = 0; k < m; k++) {
        miss[k] = (int)(rng() % 500000000u) * 2 + 1;                        // 奇数 ⇒ 一定找不到
        hit[k]  = a[1 + (int)(rng() % (unsigned)n)];
    }

    long long bruteWorst, bruteAvg, binSteps;
    double t0, msBruteWorst, msBin;

    steps = 0; t0 = now_ms();
    for (int k = 0; k < m; k++) bruteFind(miss[k]);
    msBruteWorst = now_ms() - t0; bruteWorst = steps;

    steps = 0;
    for (int k = 0; k < m; k++) bruteFind(hit[k]);
    bruteAvg = steps;

    steps = 0; t0 = now_ms();
    for (int k = 0; k < m; k++) binFind(miss[k]);
    msBin = now_ms() - t0; binSteps = steps;

    long long perQuery = binSteps / m;                                      // 每次询问几步
    long long ratio = bruteWorst / max(1LL, binSteps);

    /* 满数据（n = 10⁶、m = 10⁵）那两个数：暴力 10¹¹，二分 2×10⁶ */
    long long fullBrute = 1000000LL * 100000LL;
    long long lg = 0; for (long long x = 1000000LL; x > 0; x >>= 1) lg++;
    long long fullBin = 100000LL * lg;

    if (csv) {
        printf("n,%d\nm,%d\n", n, m);
        printf("bruteWorst,%lld\nbruteAvg,%lld\nbinSteps,%lld\n", bruteWorst, bruteAvg, binSteps);
        printf("perQuery,%lld\nratio,%lld\n", perQuery, ratio);
        printf("worstOverAvg,%.1f\n", (double)bruteWorst / (double)bruteAvg);
        printf("fullBrute,%lld\nfullBin,%lld\nfullRatio,%lld\n", fullBrute, fullBin, fullBrute / fullBin);
        return 0;
    }
    printf("n = %d、m = %d：\n\n", n, m);
    printf("  暴力（问不存在的数 = 最坏形状） %12lld 次比较   %8.1f 毫秒\n", bruteWorst, msBruteWorst);
    printf("  暴力（问真的在里面的数）       %12lld 次比较   —— 只有最坏的 1/%.1f\n",
           bruteAvg, (double)bruteWorst / (double)bruteAvg);
    printf("  二分                           %12lld 次比较   %8.1f 毫秒   每次询问 %lld 步\n",
           binSteps, msBin, perQuery);
    printf("\n  这一组数据上差 %lld 倍。\n", ratio);
    printf("\n满数据 n = 10⁶、m = 10⁵ 呢（算出来的，跑不完）：\n");
    printf("  暴力 %lld 次，二分 %lld 次 —— 差 %lld 倍。\n", fullBrute, fullBin, fullBrute / fullBin);
    return 0;
}

// 顶格数据（P2249 计时用）：`./p2249GenBig <n> <m> <level>`
//
//   level 0  值域大：a_i 随机取到 10⁹（题面顶格的样子）
//   level 1  ★ 暴力的最坏形状：**所有询问都问一个不存在的数**
//            ⇒ 第一版每次都要扫满整趟 n，一次都不能提前 break。
//
// ⚠ level 1 才是「暴力有多慢」的正确度量。用 level 0 量出来的暴力**偏快**，
//   因为随机询问平均扫到一半就撞上了 —— 而评测机上的最坏点不会这么客气。
//   （第 51 章那条「造一组大数据跑一次也不够，要造对形状」在这道题上的样子。）

#include <bits/stdc++.h>
using namespace std;

int main(int argc, char** argv) {
    int n = (argc > 1) ? atoi(argv[1]) : 1000000;
    int m = (argc > 2) ? atoi(argv[2]) : 100000;
    int level = (argc > 3) ? atoi(argv[3]) : 0;

    mt19937 rng(20260827u);
    vector<int> a(n);
    // ⚠ 上限是 5×10⁸ 再乘 2 —— 题面是 0 <= a_i <= 10⁹，取 10⁹ 再乘 2 就**越界**了
    for (int i = 0; i < n; i++) a[i] = (int)(rng() % 500000000u) * 2;    // 全偶数，留出奇数给 level 1
    sort(a.begin(), a.end());

    printf("%d %d\n", n, m);
    for (int i = 0; i < n; i++) printf("%d%c", a[i], i + 1 == n ? '\n' : ' ');
    for (int k = 0; k < m; k++) {
        int q = (level == 1) ? (int)(rng() % 500000000u) * 2 + 1         // 奇数 ⇒ 一定找不到
                             : a[rng() % (unsigned)n];
        printf("%d%c", q, k + 1 == m ? '\n' : ' ');
    }
    return 0;
}

// P2249 的第一个 WA：二分「撞上了就返回」
//
// 把上一版的顺序扫换成二分，几乎是条件反射：数组是有序的，那就折半找。
// 于是写出下面这一版 —— 它是**大多数人学二分时最先背下来的那个模板**：
//
//     while (l <= r) { mid = ...; if (a[mid] == q) return mid; ... }
//
// ⚠ 它错在哪：题目问的是「**第一次**出现的编号」，而二分撞上的那个 q
//   **可能是中间的那一个**。样例里 a = 1 3 3 3 5 …，问 3 ——
//   二分第一次就撞在下标 3 上，于是输出 3，而正确答案是 2。
//
// ★ 这就是第 8 章第 ⑤ 步那个模板要解决的事：**别去找「一个」，去找「第一个 >= q 的位置」。**
//   「相等」是可以有很多个的，「第一个 >= q」只有一个 —— 它才是可以二分的那个问题。
//
// ⚠ 更值得记的是：这个错**只在有重复元素时才现形**。
//   对拍时如果数据的值域一开就大（比如 a_i 随机取到 10⁹），
//   整个序列几乎没有重复，这一版和正解会一路一致 —— 见 p2249Gen.cpp 的两个档位。

#include <bits/stdc++.h>
using namespace std;

static int a[1000006];

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, m;
    if (!(cin >> n >> m)) return 0;
    for (int i = 1; i <= n; i++) cin >> a[i];

    for (int k = 0; k < m; k++) {
        int q;
        cin >> q;
        int ans = -1;
        int l = 1, r = n;
        while (l <= r) {
            int mid = l + (r - l) / 2;
            if (a[mid] == q) { ans = mid; break; }  // ⚠ 撞上就收工 —— 但它未必是第一个
            else if (a[mid] < q) l = mid + 1;
            else r = mid - 1;
        }
        cout << ans << ' ';
    }
    cout << '\n';
    return 0;
}

// P2249 的第二个 WA：二分对了，但忘了「有没有找到」这一问
//
// 这一版已经用上了第 8 章那个模板，`lowerPos` 一个字都没写错 ——
// 它返回的是「第一个 >= q 的位置」，重复元素的坑已经绕过去了。
//
// ⚠ 可它把返回值**直接**当成了答案。而 `lowerPos` 回答的问题是
//   「**如果** q 在，它会在哪儿」，不是「q 在不在」。
//   q 根本不存在时它照样给一个位置：
//     · q 比所有数都大 ⇒ 返回 n+1（越界的那一格）；
//     · q 落在两个数中间 ⇒ 返回右边那个数的位置，于是输出了**别人的编号**。
//
// ★ 所以模板后面永远要跟一句判等：`if (L <= n && a[L] == q)`。
//   两件事分开做 —— **二分负责定位，判等负责回答「在不在」**。
//
// ⚠ 这一版和 p2249Wrong.cpp 互为盲区（第 7 章 P1638/P1873 那条的第三次复现）：
//   全是重复元素、询问必定命中的数据能把 Wrong 抓出来，却一次也抓不到它；
//   要抓它，生成器必须**故意问不存在的数**。

#include <bits/stdc++.h>
using namespace std;

static int a[1000006];
static int n;

static int lowerPos(int x) {                        // 第一个 >= x 的位置，没有就是 n+1
    int l = 1, r = n + 1;
    while (l < r) {
        int mid = l + (r - l) / 2;
        if (a[mid] >= x) r = mid;
        else l = mid + 1;
    }
    return l;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int m;
    if (!(cin >> n >> m)) return 0;
    for (int i = 1; i <= n; i++) cin >> a[i];

    for (int k = 0; k < m; k++) {
        int q;
        cin >> q;
        cout << lowerPos(q) << ' ';                 // ⚠ 少了那一句判等
    }
    cout << '\n';
    return 0;
}

// P2249 查找 —— ★ 这一版就已经能 AC 了
//
// 一句话：**把「找 q」换成「找第一个 >= q 的位置」，再补一句判等。**
//
//   L = lowerPos(q)                     ← 第 8 章第 ⑤ 步那个模板，一个字没改
//   if (L <= n && a[L] == q) 输出 L     ← 判等负责回答「在不在」
//   else                     输出 -1
//
// 为什么这样就同时解决了两个坑：
//   · 「第一次出现」：`lowerPos` 找的是**第一个** >= q 的位置，
//     q 有多少个重复都不影响它 —— 它天生停在这一段的左端点；
//   · 「找不到输出 -1」：判等那一句管的。⇒ 见 p2249Wrong.cpp / p2249NoEq.cpp 各错了哪一半。
//
// 复杂度：每次询问 O(log n)，总共 m log n ≈ 10⁵ × 20 = 2×10⁶ 次比较，
// 而第一版是 10¹¹ 次 —— **差五万倍**（这笔账在 p2249Count.cpp 里）。
//
// ⚠ 题面写着「本题输入输出量较大，请使用较快的 IO 方式」。
//   这里用的是最省事的那一档：`ios::sync_with_stdio(false)` + `cin.tie(nullptr)`。
//   到底要不要更快的，别猜 —— p2249Read.cpp 把四种读法在这道题的规模上量了一遍。

#include <bits/stdc++.h>
using namespace std;

static int a[1000006];
static int n;

/** 第一个 >= x 的位置；全都比 x 小就返回 n+1 */
static int lowerPos(int x) {
    int l = 1, r = n + 1;
    while (l < r) {
        int mid = l + (r - l) / 2;
        if (a[mid] >= x) r = mid;       // mid 够大了，答案在 mid 或它左边
        else l = mid + 1;               // mid 太小，扔掉
    }
    return l;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int m;
    if (!(cin >> n >> m)) return 0;
    for (int i = 1; i <= n; i++) cin >> a[i];

    for (int k = 0; k < m; k++) {
        int q;
        cin >> q;
        int L = lowerPos(q);
        cout << ((L <= n && a[L] == q) ? L : -1) << ' ';
    }
    cout << '\n';
    return 0;
}

// P2249 —— 同一件事交给标准库：std::lower_bound
//
// `lower_bound(first, last, x)` 返回的正是「第一个 >= x 的位置」的**迭代器**，
// 和 p2249.cpp 里手写的 `lowerPos` 是同一个语义、同一个复杂度。
//
//   auto it = lower_bound(a + 1, a + n + 1, q);
//   if (it != a + n + 1 && *it == q) 输出 it - a;      ← 判等那一句照样不能省
//   else                             输出 -1;
//
// ★ 那为什么还要手写一遍？两个理由：
//   ① 手写那一版能让你看清「第一次出现」是**怎么**被找出来的（第 ⑤ 步那个模板）；
//   ② 到了下一章「二分答案」，要二分的东西不在数组里（是答案本身），
//      标准库那一套就用不上了 —— 模板才是能带走的东西。
//
// ⚠ 两版必须逐字节一致，这条写成断言钉在 check:viz 里。

#include <bits/stdc++.h>
using namespace std;

static int a[1000006];

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, m;
    if (!(cin >> n >> m)) return 0;
    for (int i = 1; i <= n; i++) cin >> a[i];

    for (int k = 0; k < m; k++) {
        int q;
        cin >> q;
        int* it = lower_bound(a + 1, a + n + 1, q);
        cout << ((it != a + n + 1 && *it == q) ? (int)(it - a) : -1) << ' ';
    }
    cout << '\n';
    return 0;
}

// 数据生成器（P2249 对拍用）：`./p2249Gen <seed> [level]`
//
// 两个 WA 版要**两种完全不同的数据**才抓得到，这个生成器就是为这件事分的档：
//
//   level 0（默认）**值域压到很小**：n <= 12、a_i ∈ [0, 5]，询问必定命中
//                  ⇒ 重复元素满地都是，专抓 p2249Wrong（撞上就返回，返回的不是第一个）
//   level 1        **值域放大**：n <= 12、a_i ∈ [0, 10⁹]，询问仍必定命中
//                  ⇒ 几乎没有重复，Wrong 那一版会一路正确 —— 这是它的**盲区对照**
//   level 2        **故意问不存在的数**：a_i 全取偶数，询问全取奇数
//                  ⇒ 每次都得输出 -1，专抓 p2249NoEq（忘了判等）
//   level 3        ★ **「顺手写」的那一版**：n <= 12、a_i 和询问都在 [0, 10⁹] 里随便取。
//                  这是没想清楚时真实会写出来的生成器 —— 留着它是为了量出
//                  「不调生成器的话，这两个 bug 各能被抓到多少」。
//
// ★ 两个档位互为盲区，这正是第 7 章 P1638 / P1873 学到的那条：
//   **为一个 bug 精心造的档位，往往正是另一个 bug 的盲区。**
//   （level 0 抓不到 NoEq —— 因为询问必定命中，判不判等结果一样；
//     level 2 抓不到 Wrong —— 因为根本没有「相等」这件事发生。）
//
// ⚠ 序列必须**单调不减**，这是题面的前提；造完一定要排序，否则两个程序会
//   「一致地输出垃圾」，看着全绿其实什么都没验。

#include <bits/stdc++.h>
using namespace std;

static mt19937 rng;
static int ri(int lo, int hi) { return lo + (int)(rng() % (unsigned)(hi - lo + 1)); }

int main(int argc, char** argv) {
    unsigned seed = (argc > 1) ? (unsigned)atoi(argv[1]) : 1;
    int level = (argc > 2) ? atoi(argv[2]) : 0;
    rng.seed(seed);

    int n = ri(1, 12);
    int m = ri(1, 6);
    vector<int> a(n);

    if (level == 1 || level == 3) {
        for (int i = 0; i < n; i++) a[i] = ri(0, 1000000000);
    } else if (level == 2) {
        for (int i = 0; i < n; i++) a[i] = ri(0, 500000000) * 2;     // 全是偶数
    } else {
        for (int i = 0; i < n; i++) a[i] = ri(0, 5);                 // 值域只有 6 个数
    }
    sort(a.begin(), a.end());

    printf("%d %d\n", n, m);
    for (int i = 0; i < n; i++) printf("%d%c", a[i], i + 1 == n ? '\n' : ' ');
    for (int k = 0; k < m; k++) {
        int q;
        if (level == 2)      q = ri(0, 500000000) * 2 + 1;           // 全是奇数 ⇒ 必定不存在
        else if (level == 3) q = ri(0, 1000000000);                  // 顺手：随便取
        else                 q = a[ri(0, n - 1)];                    // 从序列里挑 ⇒ 必定命中
        printf("%d%c", q, k + 1 == m ? '\n' : ' ');
    }
    return 0;
}

// P2249 的第二关：题面那句「请使用较快的 IO」到底虚不虚
//
// 用法：./p2249Read [n] [m] [csv]      默认就是满数据 n = 10⁶、m = 10⁵
//   ★ 它自己造一份 P2249 形状的输入写进临时文件，再 freopen 回 stdin 读四遍 ——
//     不需要喂输入。四遍算出来的**校验和必须一模一样**（csv 里的 same 钉这件事）。
//
// 四种读法（第 45 章第 11 步解释过它们的区别，这里量的是**这道题上的**代价）：
//   ① cin（默认，同步开着）    ② cin + sync_with_stdio(false)
//   ③ scanf                    ④ 手写快读（fread 整块读进来自己拼数字）
//
// ⚠ 顺序不能换：关掉同步之后 cin 会自己预读一大块，之后再 freopen 换文件，
//   cin 缓冲里剩的就是上一份文件的残渣 ⇒ 「同步开着」那一趟必须排在最前面
//   （第 45 章 read.cpp、第 6 章 p2367Read.cpp 都踩过这条，照抄它们的顺序）。
//
// ★ 要看的是**绝对毫秒数**，不是倍数 —— 第 7 章学到的：
//   倍数跨题几乎不变，而「够不够」比的是绝对时间和那 1 秒的时限。

#include <bits/stdc++.h>
#include <chrono>
using namespace std;
using namespace std::chrono;

static char path[64];
static int a[1000006];
static int n, m;

static void makeData(int nn, int mm) {
    snprintf(path, sizeof(path), "/tmp/p2249-bench-%d.txt", (int)getpid());
    FILE* f = fopen(path, "w");
    if (!f) { fprintf(stderr, "写不出临时文件 %s\n", path); exit(1); }
    mt19937 rng(20260827u);
    vector<int> v(nn);
    for (int i = 0; i < nn; i++) v[i] = (int)(rng() % 1000000001u);   // 0 <= a_i <= 10⁹，含上界
    sort(v.begin(), v.end());
    fprintf(f, "%d %d\n", nn, mm);
    for (int i = 0; i < nn; i++) fprintf(f, "%d%c", v[i], i + 1 == nn ? '\n' : ' ');
    for (int k = 0; k < mm; k++) {
        int q = (rng() & 1u) ? v[rng() % (unsigned)nn] : (int)(rng() % 1000000000u);
        fprintf(f, "%d%c", q, k + 1 == mm ? '\n' : ' ');
    }
    fclose(f);
}
static void reopen() {
    if (!freopen(path, "r", stdin)) { fprintf(stderr, "读不回临时文件\n"); exit(1); }
}

/* 二分那几行 —— 四趟共用，所以四趟之间的差别只可能来自读入 */
static int lowerPos(int x) {
    int l = 1, r = n + 1;
    while (l < r) {
        int mid = l + (r - l) / 2;
        if (a[mid] >= x) r = mid;
        else l = mid + 1;
    }
    return l;
}
static long long answerFor(int q) {
    int L = lowerPos(q);
    return (L <= n && a[L] == q) ? L : -1;
}

static char ibuf[1 << 22];
static size_t ipos = 0, ilen = 0;
static inline int gc() {
    if (ipos == ilen) { ilen = fread(ibuf, 1, sizeof(ibuf), stdin); ipos = 0; if (!ilen) return EOF; }
    return ibuf[ipos++];
}
static inline int readIntFast() {
    int c = gc(), x = 0;
    while (c != EOF && (c < '0' || c > '9')) c = gc();
    for (; c >= '0' && c <= '9'; c = gc()) x = x * 10 + (c - '0');
    return x;
}

int main(int argc, char** argv) {
    int nn = (argc > 1) ? atoi(argv[1]) : 1000000;
    int mm = (argc > 2) ? atoi(argv[2]) : 100000;
    bool csv = (argc > 3 && string(argv[3]) == "csv");
    makeData(nn, mm);
    double ms[4];
    long long sum[4];

    /* ① cin（默认，同步开着）—— 必须排第一趟 */
    { reopen();
      auto t0 = steady_clock::now();
      cin >> n >> m;
      for (int i = 1; i <= n; i++) cin >> a[i];
      long long s = 0;
      for (int k = 0; k < m; k++) { int q; cin >> q; s += answerFor(q); }
      sum[0] = s;
      ms[0] = duration<double, milli>(steady_clock::now() - t0).count(); }

    /* ② cin + sync_with_stdio(false) */
    { reopen();
      auto t0 = steady_clock::now();
      ios::sync_with_stdio(false); cin.tie(nullptr);
      cin >> n >> m;
      for (int i = 1; i <= n; i++) cin >> a[i];
      long long s = 0;
      for (int k = 0; k < m; k++) { int q; cin >> q; s += answerFor(q); }
      sum[1] = s;
      ms[1] = duration<double, milli>(steady_clock::now() - t0).count(); }

    /* ③ scanf */
    { reopen();
      auto t0 = steady_clock::now();
      if (scanf("%d %d", &n, &m) != 2) { n = m = 0; }
      for (int i = 1; i <= n; i++) { if (scanf("%d", &a[i]) != 1) break; }
      long long s = 0;
      for (int k = 0; k < m; k++) { int q; if (scanf("%d", &q) != 1) break; s += answerFor(q); }
      sum[2] = s;
      ms[2] = duration<double, milli>(steady_clock::now() - t0).count(); }

    /* ④ 手写快读 */
    { reopen(); ipos = ilen = 0;
      auto t0 = steady_clock::now();
      n = readIntFast(); m = readIntFast();
      for (int i = 1; i <= n; i++) a[i] = readIntFast();
      long long s = 0;
      for (int k = 0; k < m; k++) s += answerFor(readIntFast());
      sum[3] = s;
      ms[3] = duration<double, milli>(steady_clock::now() - t0).count(); }

    remove(path);
    bool same = (sum[0] == sum[1] && sum[1] == sum[2] && sum[2] == sum[3]);
    if (csv) {
        const char* key[4] = { "cin", "nosync", "scanf", "fast" };
        for (int k = 0; k < 4; k++) printf("%s,%.1f\n", key[k], ms[k]);
        printf("same,%d\nchecksum,%lld\n", same ? 1 : 0, sum[0]);
        return 0;
    }
    const char* name[4] = { "cin（默认，同步开着）", "cin + sync_with_stdio(false)",
                            "scanf", "手写快读（fread）" };
    /* ⚠ 中文是双宽的，%-30s 按字节数补空格会补歪 —— 照第 45 章 read.cpp 那套按显示宽度补 */
    auto disp = [](const string& t) {
        int w = 0;
        for (unsigned char c : t) { if ((c & 0xC0) == 0x80) continue; w += (c < 0x80) ? 1 : 2; }
        return w;
    };
    auto padR = [&](const string& t, int w) { return t + string(max(0, w - disp(t)), ' '); };
    double best = *min_element(ms, ms + 4);
    printf("n = %d、m = %d（一共要读 %d 个整数），四种读法跑同一个二分：\n\n", nn, mm, nn + mm + 2);
    for (int k = 0; k < 4; k++)
        printf("  %s %8.1f 毫秒   慢 %4.1f 倍\n", padR(name[k], 30).c_str(), ms[k], ms[k] / best);
    printf("\n四趟的校验和%s（都是 %lld）\n", same ? "完全一致" : "居然不一致！", sum[0]);
    printf("⚠ 时限是 1 秒 —— 要看的是上面那列**毫秒数**离 1000 还有多远，不是倍数。\n");
    return 0;
}