洛谷 P1469 找筷子

// P1469 ✗ 排序版：**答案是对的** —— 它挂在题面那行「空间限制 8 Mb」上
//
// ★ 它就是[第 46 章正文第 3 步](/ch/46-bitwise/)那份 sortPair.cpp，正文里写的是「✓ 能过」。
//   那句话没错 —— 因为正文那道题是 m ≤ 2×10⁶+1、内存 **256 MiB**。
//   换到真题（n ≤ 10⁷+1、内存 **8 MiB**）上：
//       (10⁷+1) 个 int = 40 000 004 字节 = **38.15 MiB**，而限制是 8 MiB
//   ⇒ 光是「把数据存下来」这一步就超了 **4.8 倍**，排序还没开始。
//
// ⚠⚠ 这一版是这一页的主角，因为它演示的是一整类事故：
//   **答案对、样例过、对拍 300 轮 0 次不一致，而它在评测机上一分都拿不到。**
//   ⇒ 「答案对但跑不完（装不下）」只能靠**算**发现（[第 20 章 P5019](/sol/p5019/) 那条）。
#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false); cin.tie(nullptr);
    int n; if (!(cin >> n)) return 0;
    vector<int> a(n);                     // ⚠ 就是这一行：n = 10⁷+1 时它要 38.15 MiB
    for (int i = 0; i < n; i++) cin >> a[i];
    sort(a.begin(), a.end());
    for (int i = 0; i + 1 < n; i += 2)
        if (a[i] != a[i + 1]) { cout << a[i] << '\n'; return 0; }
    cout << a[n - 1] << '\n';             // ★ 前面全成对 ⇒ 落单的排在最后（p1469Last 少的就是这一行）
    return 0;
}

// P1469 ✗ 错法二：「落单」读成了「只出现一次」
//
// ⚠⚠ 题面写的是「这些筷子中**只有一只筷子是落单的**，其余都成双」——
//   它说的是**筷子**落单，不是**长度**只出现一次。
//   同一个长度完全可以出现 3 根（一双 + 那只落单的），别的长度也可以出现 4 根（两双）。
//
// ★★★ 而**官方样例就是照着这个坑造的**：
//       9 / 2 2 1 3 3 3 2 3 1   ⇒  2 出现 3 次、3 出现 4 次、1 出现 2 次，答案是 2
//   ⇒ 这一版在样例上找不到任何「只出现一次」的长度，当场打出 0。
//
// ★ 它靠什么现形：**落单的那个长度出现次数 ≥ 3**。
//   ⚠ 而顺手写的生成器（k 对 + 1 根落单）**一辈子造不出这一档** ⇒ 档 0 是**结构性的精确的 0**。
//   ⇒ 「[样例比对拍还狠](/sol/p1217/)」的又一次，而这次原因很具体：
//     出题人是照着题面那句话挑的样例，随机生成器不会。
#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false); cin.tie(nullptr);
    int n; if (!(cin >> n)) return 0;
    map<int, int> cnt;
    for (int i = 0; i < n; i++) { int x; cin >> x; cnt[x]++; }
    for (auto& kv : cnt)
        if (kv.second == 1) { cout << kv.first << '\n'; return 0; }   // ⚠ 就是这个 == 1
    cout << 0 << '\n';
    return 0;
}

// P1469 找筷子 —— 正解：一个变量，一个循环，边读边算
//
// ★★★ 这道题和[第 46 章正文](/ch/46-bitwise/)那道是同一道，但**题面那两行限制不一样**：
//     正文那份是「m ≤ 2×10⁶+1、长度 ≤ 10⁸、内存 256 MiB」，
//     真题是      「n ≤ 10⁷+1、a_i ≤ 10⁹、内存 **8192 KB = 8 MiB**、时限 2 秒」。
//   ⇒ 正文第 7 步那张四行表上「✓ 能过」的排序版，在真题上是 **MLE**（见 p1469Sort.cpp）。
//
// ⚠ 所以这一份有两处是被那 8 MiB 逼出来的，不是为了炫技：
//   ① **一个数组都不开** —— 异或天生就是边读边算，峰值内存和 n 无关；
//   ② 快读的缓冲区只开 **64 KiB**。⚠⚠ 顶格输入约 94 MB（随机数据实测 98 707 677 字节；
//      每个数都顶到 10 位那种极端情形约 110 MB），
//      「一次性 fread 整个文件」那种常见模板在这道题上直接 MLE（见 p1469Whole.cpp），
//      而缓冲区哪怕开到 4 MiB，加上进程本身那 ~4 MiB 就已经在和 8 MiB 赛跑了。
//      ⇒ 要的是「读完就续」的**窗口**，不是「一次读完」的桶。
#include <cstdio>
using namespace std;

static char buf[1 << 16];                 // ⚠ 64 KiB —— 这道题里缓冲区大小是有上限的
static size_t bpos = 0, blen = 0;
static inline int gc() {
    if (bpos == blen) { blen = fread(buf, 1, sizeof(buf), stdin); bpos = 0; if (!blen) return EOF; }
    return buf[bpos++];
}
static inline int readInt() {
    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 n = readInt();
    int res = 0;                          // ★ 初值必须是 0：它是异或的单位元（a ^ 0 = a）
    for (int i = 0; i < n; i++) res ^= readInt();
    printf("%d\n", res);
    return 0;
}

// P1469 的第一道门槛：把 10⁷+1 个数读进来（题面【提示】自己点了名的那件事）
//
// 用法：./p1469Read [n]        人话版（默认题面顶格 n = 10⁷+1）
//       ./p1469Read [n] csv    给 check:viz 用
//
// ★ 先算一笔账（[第 10 章 P1271](/sol/p1271/) 那把尺子：**字节数**，不是数的个数）：
//   n = 10⁷+1 个数、每个 a_i ≤ 10⁹ ⇒ 平均 9 位多 + 一个分隔符 ≈ 每个数 10 字节
//   ⇒ 输入约 **94 MB**（本文件实测 98 707 677 字节）。这是全书最大的一次读入
//     （[第 12 章 P1923](/sol/p1923/) 那次是 48 MB）。
//
// ⚠⚠ 而这道题的内存限制是 **8192 KB = 8 MiB** ⇒ 那 94 MB **不许整个进内存**。
//   所以这张表里第 ④ 行是「fread **窗口**」（64 KiB，读完就续），
//   不是网上最流行的「一次性 fread 整个文件」—— 那一份在这道题上光缓冲区就超 11.8 倍。
//
// ⚠ 这份程序自己造数据写进临时文件，再 freopen 回来读 —— 不需要喂输入。
// ⚠ 「同步开着」那一趟必须排最前面（关掉同步之后 cin 会预读，换文件会读到残渣）。
// ★★ 每一档跑 3 次取中位数，而且断言只钉**倍数**、不钉秒数
//   —— 硬规矩第 5 条，代价见 [P1923](/sol/p1923/) 那两次翻红。
#include <bits/stdc++.h>
#include <chrono>
using namespace std;
using namespace std::chrono;

static char path[64];

static void makeData(int nn) {
    snprintf(path, sizeof(path), "/tmp/p1469-bench-%d.txt", (int)getpid());
    FILE* f = fopen(path, "w");
    if (!f) { fprintf(stderr, "写不出临时文件\n"); exit(1); }
    mt19937 rng(20260906u);
    fprintf(f, "%d\n", nn);
    for (int i = 0; i < nn; i++)
        fprintf(f, "%u%c", (unsigned)(rng() % 1000000000u) + 1, i + 1 == nn ? '\n' : ' ');
    fclose(f);
}
static void reopenIn() { if (!freopen(path, "r", stdin)) { fprintf(stderr, "读不回临时文件\n"); exit(1); } }

static char ibuf[1 << 16];                 // ★ 64 KiB 的**窗口**（正解用的就是这个大小）
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 n = (argc > 1) ? atoi(argv[1]) : 10000001;
    bool csv = (argc > 2 && string(argv[2]) == "csv");
    makeData(n);

    long long bytes = 0;
    { FILE* f = fopen(path, "rb"); fseek(f, 0, SEEK_END); bytes = ftell(f); fclose(f); }
    double mb = (double)bytes / 1048576.0;

    const int REP = 3;
    double rep[4][REP]; int res[4] = {0, 0, 0, 0};
    const char* NAME[4] = { "cin 默认（同步开着）", "cin 关同步", "scanf", "fread 窗口快读（64 KiB）" };
    auto median3 = [](double* a) { double x = a[0], y = a[1], z = a[2];
        return max(min(x, y), min(max(x, y), z)); };

    for (int r = 0; r < REP; r++) {
        reopenIn(); auto t0 = steady_clock::now(); int s = 0;
        int nn; cin >> nn; for (int i = 0; i < n; i++) { int x; cin >> x; s ^= x; }
        rep[0][r] = duration<double, milli>(steady_clock::now() - t0).count(); res[0] = s; }

    ios::sync_with_stdio(false); cin.tie(nullptr);
    for (int r = 0; r < REP; r++) {
        reopenIn(); auto t0 = steady_clock::now(); int s = 0;
        int nn; cin >> nn; for (int i = 0; i < n; i++) { int x; cin >> x; s ^= x; }
        rep[1][r] = duration<double, milli>(steady_clock::now() - t0).count(); res[1] = s; }

    for (int r = 0; r < REP; r++) {
        reopenIn(); auto t0 = steady_clock::now(); int s = 0;
        int nn; if (scanf("%d", &nn) != 1) return 1;
        for (int i = 0; i < n; i++) { int x; if (scanf("%d", &x) != 1) return 1; s ^= x; }
        rep[2][r] = duration<double, milli>(steady_clock::now() - t0).count(); res[2] = s; }

    for (int r = 0; r < REP; r++) {
        reopenIn(); ipos = ilen = 0; auto t0 = steady_clock::now(); int s = 0;
        int nn = readIntFast(); (void)nn;
        for (int i = 0; i < n; i++) s ^= readIntFast();
        rep[3][r] = duration<double, milli>(steady_clock::now() - t0).count(); res[3] = s; }

    remove(path);
    double ms[4]; for (int i = 0; i < 4; i++) ms[i] = median3(rep[i]);
    bool same = (res[0] == res[1] && res[1] == res[2] && res[2] == res[3]);

    if (csv) {
        printf("n,%d\n", n);
        printf("bytes,%lld\n", bytes);
        printf("mb,%.1f\n", mb);
        for (int i = 0; i < 4; i++) printf("ms%d,%.0f\n", i, ms[i]);
        /* ★★ 断言只钉**倍数**和**量级带**，不钉秒数，更不钉「有没有跨过 2000」——
           默认 cin 实测就在 2000 上下（余量不到 5%），那种布尔量会被并行负载晃翻
           （[P1923](/sol/p1923/) 两次翻红换来的教训）。 */
        printf("ratioSync,%.2f\n", ms[0] / ms[1]);     // 默认 cin / 关同步
        printf("ratioScanf,%.2f\n", ms[0] / ms[2]);    // 默认 cin / scanf
        printf("ratioFast,%.2f\n", ms[0] / ms[3]);     // 默认 cin / 快读
        printf("syncBand,%d\n", (ms[0] > 1200.0 && ms[0] < 6000.0) ? 1 : 0);   // 默认 cin 在「秒」这个量级上
        printf("othersFit,%d\n", (ms[1] < 500.0 && ms[2] < 500.0 && ms[3] < 500.0) ? 1 : 0);
        printf("same,%d\n", same ? 1 : 0);
        printf("wholeMiB,%.1f\n", mb);                 // 一次性读完至少要这么大的缓冲区
        printf("limitMiB,%.1f\n", 8192.0 / 1024.0);
        return 0;
    }

    printf("P1469 读入这一关：n = %d，输入 %lld 字节（%.1f MB），时限 2 秒\n\n", n, bytes, mb);
    for (int i = 0; i < 4; i++)
        printf("  %s：%.0f 毫秒（%s）\n", NAME[i], ms[i], ms[i] < 2000.0 ? "够" : "★ 不够");
    printf("\n  四种读法结果一致：%s\n", same ? "是" : "★★ 否（有一份少读了）");
    printf("  默认 cin / 关同步 = %.2f 倍；/ scanf = %.2f 倍；/ 快读 = %.2f 倍\n",
           ms[0] / ms[1], ms[0] / ms[2], ms[0] / ms[3]);
    printf("  ⚠ 默认 cin 正好压在时限线上（余量不到 5%%）⇒ 别把结论写成「它一定 TLE」，\n");
    printf("    该写的是「它比关同步慢六倍多，而你根本没有六倍可以浪费」。\n");
    printf("\n  ⚠ 「一次性 fread 整个文件」那种模板：缓冲区至少要 %.1f MiB，而内存限制是 8.0 MiB\n", mb);
    return 0;
}

// P1469 解析页上所有数字的出处。
//   ./p1469Count            人话版（内存账 + 触发线）
//   ./p1469Count csv        给 check:viz 用
//   ./p1469Count mem xor    ★ 真跑一遍顶格的异或版，打「峰值 − 起步」
//   ./p1469Count mem sort   ★ 真跑一遍顶格的排序版，打「峰值 − 起步」
//
// ⚠⚠⚠ 为什么这里报的是**差值**而不是峰值（2026-09-06 撞出来的）：
//   `ru_maxrss` 里有一截是「进程起步」，而**那一截不是程序的属性 —— 它取决于谁 spawn 它**。
//   同一个二进制、同一份环境变量：从 shell 里跑起步 **3.7 MiB**，被 node 起来是 **8.4 MiB**。
//   ⇒ 拿峰值写断言，`check:viz` 里就会得出「异或版也 MLE」这种结论（真踩过一次）。
//   ⇒ 稳的是**差值**：它就是这份程序自己申请的那些内存，跨宿主不变。
//
// 三件事：
//   ① ★★★ **内存账** —— 这道题真正的关卡。题面写的是「8192 KB」，按 KB 读就是 **8 MiB**
//      （[第 41 章那条](/sol/p1865/)：转录题面时时限和内存都要连单位一起抄）。
//      四种做法各要多少，全是一句乘法，动手之前就能算完。
//   ② 两个错法的**触发线**，以及官方样例落在哪一侧。
//   ③ 题面那句「对于 30% 的数据 n ≤ 10⁵」——⇒ 出题人把暴力那一档也写好了
//      （[第 24 章 P1776](/sol/p1776/) 那条）。
#include <bits/stdc++.h>
#include <sys/resource.h>
using namespace std;

static double peakMiB() {
    struct rusage ru; getrusage(RUSAGE_SELF, &ru);
    return (double)ru.ru_maxrss / 1024.0;                 // Linux 上 ru_maxrss 的单位是 KiB
}

static const long long NMAX = 10000001LL;                 // 题面顶格 n = 10⁷ + 1
static const long long VMAX = 1000000000LL;               // 题面顶格 a_i ≤ 10⁹
static const double LIMIT = 8192.0 / 1024.0;              // 8192 KB = 8.0 MiB

int main(int argc, char** argv) {
    string mode = argc > 1 ? argv[1] : "";

    if (mode == "mem") {
        string which = argc > 2 ? argv[2] : "xor";
        double before = peakMiB();
        mt19937 rng(20260906u);
        if (which == "sort") {
            vector<int> a((size_t)NMAX);
            for (long long i = 0; i < NMAX; i++) a[(size_t)i] = (int)(rng() % 1000000000u) + 1;
            sort(a.begin(), a.end());
            double now = peakMiB();
            printf("sort 版（把 %lld 个 int 存下来再排序）：自己要了 %.1f MiB"
                   "（峰值 %.1f − 起步 %.1f）；限制 %.1f MiB ⇒ %s\n",
                   NMAX, now - before, now, before, LIMIT, now - before > LIMIT ? "★ MLE" : "够");
        } else {
            int res = 0;
            for (long long i = 0; i < NMAX; i++) res ^= (int)(rng() % 1000000000u) + 1;
            double now = peakMiB();
            printf("xor 版（边读边算，一个数组都不开）：自己要了 %.1f MiB"
                   "（峰值 %.1f − 起步 %.1f）；限制 %.1f MiB ⇒ %s（res=%d）\n",
                   now - before, now, before, LIMIT, now - before > LIMIT ? "★ MLE" : "够", res);
        }
        return 0;
    }

    /* ---------- ① 内存账：四种做法，全是一句乘法 ---------- */
    double mSort = (double)NMAX * 4.0 / 1048576.0;                 // 存 n 个 int
    double mBucketInt = (double)(VMAX + 1) * 4.0 / 1073741824.0;   // int  桶（GiB）
    double mBucketChar = (double)(VMAX + 1) / 1048576.0;           // char 桶（MiB）
    double mMap = (double)((NMAX + 1) / 2) * 48.0 / 1048576.0;     // map 节点按 48 字节算
    double mSub = (double)100000 * 4.0 / 1048576.0;                // 30% 那一档存下来要多少

    /* ---------- ② 触发线：官方样例 ---------- */
    int sample[] = {2, 2, 1, 3, 3, 3, 2, 3, 1};
    map<int, int> c; for (int v : sample) c[v]++;
    int lone = 0, mx = 0;
    for (auto& kv : c) { if (kv.second % 2) lone = kv.first; mx = max(mx, kv.first); }
    int loneCnt = c[lone];

    if (mode == "csv") {
        printf("memSort,%.2f\n", mSort);
        printf("memBucketInt,%.2f\n", mBucketInt);
        printf("memBucketChar,%.0f\n", mBucketChar);
        printf("memMap,%.0f\n", mMap);
        printf("memSub,%.2f\n", mSub);
        printf("limit,%.1f\n", LIMIT);
        printf("overSort,%.2f\n", mSort / LIMIT);
        printf("sampleLone,%d\n", lone);
        printf("sampleLoneCnt,%d\n", loneCnt);
        printf("sampleMax,%d\n", mx);
        printf("sampleOnceDies,%d\n", loneCnt >= 3 ? 1 : 0);
        printf("sampleLastDies,%d\n", lone == mx ? 1 : 0);
        printf("subFits,%d\n", mSub < LIMIT ? 1 : 0);
        return 0;
    }

    printf("P1469 的关卡在内存上：题面写「8192 KB」= %.1f MiB，n 顶格 %lld，a_i ≤ %lld\n\n", LIMIT, NMAX, VMAX);
    printf("  ✗ 存下来再排序   %.2f MiB   ⇒ 超 %.2f 倍（正文第 3 步说「能过」的那一份）\n", mSort, mSort / LIMIT);
    printf("  ✗ int 值域桶      %.2f GiB\n", mBucketInt);
    printf("  ✗ char 值域桶     %.0f MiB\n", mBucketChar);
    printf("  ✗ map 计数        约 %.0f MiB（按每个节点 48 字节算）\n", mMap);
    printf("  ★ 异或            一个 int —— 和 n 完全无关\n\n");
    printf("  ★ 而题面「30%% 的数据 n ≤ 10⁵」那一档：存下来只要 %.2f MiB ⇒ 排序版稳拿 30 分\n\n", mSub);
    printf("  官方样例：落单的是 %d（出现 %d 次），最大值是 %d\n", lone, loneCnt, mx);
    printf("    ⇒ 「只出现一次」那个错法：%s\n", loneCnt >= 3 ? "★ 一测就死" : "放过");
    printf("    ⇒ 「漏了落单在最后」那个错法：%s\n", lone == mx ? "★ 一测就死" : "⚠ 放过（落单的不是最大值）");
    return 0;
}