太棒了！自己编写数据生成器，是你从“答题者”蜕变为“出题人”的关键一步。

对于这道题，我们面临和之前一样的情况：题目原定的数据范围 $N, M \le 1000$ 实在太温柔了！在这个范围内，$O(N \times M)$ 的双重循环暴力搜索最多只需执行 $10^6$ 次，任何正常的评测机都会让它瞬间拿到 100 分。

为了满足你**“让暴力解法能部分 AC 但不能全部 AC”的要求，我们在保证前几个测试点完全符合原题意的前提下，必须在最后几个测试点偷偷“超纲”**，把 $N$ 和 $M$ 放大到 $10^5$ 级别。在这个级别下：

• 新手暴力解法 $O(N \times M)$ 需要查找 $10^{10}$ 次，绝对会因为超时（TLE）而挂掉。
• 标答哈希解法 $O(N + M)$ 只需要 $2 \times 10^5$ 次操作，依然 $1$ 毫秒极速 AC！

同时，为了满足你对**文件大小（理想值 2MB 内）**的要求，$10^5$ 个整数以空格分隔，产生的文件大小约为 500 KB ~ 600 KB，完美符合极其轻量化的标准！

核心设计思路（10 个测试点分布）

1. Test 1 (N=3)：样例 1。完全乱序但全员到齐。
2. Test 2 (N=3)：样例 2。极端重复报数，大量缺席。
3. Test 3 (N=2)：极小边界。班上只有两人，且只有一人报数。
4. Test 4 (N=100)：局部重复。前 50 次全报 0，后 50 次全报 1，测试去重逻辑。
5. Test 5 (N=500)：常规区间。所有人刚好都报了一次（全员到齐），打乱顺序。
6. Test 6 (N=1000)：符合原题最大数据限制。纯随机缺席测试。
7. Test 7 (N=1000)：符合原题最大数据限制。全员到齐的随机报数。
8. Test 8 (N=50000)：【区分度杀手数据 1】。开始卡时间！纯随机报数，包含大量缺席。暴力法需要执行 $2.5 \times 10^9$ 次对比，极大概率 TLE。
9. Test 9 (N=100000)：【区分度杀手数据 2】。十万级别全员到齐打乱顺序。暴力法需要执行 $10^{10}$ 次对比，必定 TLE！
10. Test 10 (N=100000)：【终极杀手数据】。十万级别，但所有人全都报了同一个人的编号 N-1！这是暴力法双重循环的最坏情况（每次内层遍历都要一直走到最后才能判断没找到），专门惩罚没写 break 或算法低效的代码。

数据生成器完整 C++ 代码 (generator.cpp)

请将以下代码保存为 generator.cpp，本地编译运行即可生成完美的测试数据。

#include <iostream>
#include <fstream>
#include <vector>
#include <string>
#include <random>
#include <algorithm>
#include <numeric>

using namespace std;

// 标程：极速 O(N+M) 哈希桶算法
// 返回一个 vector，如果全员到达，返回一个特殊的 {-1} 标志
vector<int> solve(int n, int m, const vector<int>& reports) {
    vector<bool> present(n, false);
    int count = 0;
    for (int x : reports) {
        if (!present[x]) {
            present[x] = true;
            count++;
        }
    }
    
    if (count == n) {
        return {-1}; // 代表全员到齐
    }
    
    vector<int> missing;
    for (int i = 0; i < n; ++i) {
        if (!present[i]) {
            missing.push_back(i);
        }
    }
    return missing;
}

int main() {
    // 优化系统 IO 速度
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    mt19937 rng(42); // 固定随机种子以保证每次生成的数据一致

    vector<int> Ns = {3, 3, 2, 100, 500, 1000, 1000, 50000, 100000, 100000};
    vector<int> Ms = {3, 5, 2, 100, 500, 1000, 1000, 50000, 100000, 100000};
    vector<vector<int>> reports(10);

    // Test 1: 样例 1 (0 2 1)
    reports[0] = {0, 2, 1};

    // Test 2: 样例 2 (0 0 0 0 0)
    reports[1] = {0, 0, 0, 0, 0};

    // Test 3: 极小边界
    reports[2] = {1, 1};

    // Test 4: 极端两极分化
    reports[3].assign(100, 0);
    for(int i = 50; i < 100; ++i) reports[3][i] = 1;

    // Test 5: 所有人刚好一次，打乱顺序
    reports[4].resize(500);
    iota(reports[4].begin(), reports[4].end(), 0); // 填充 0~499
    shuffle(reports[4].begin(), reports[4].end(), rng);

    // Test 6: 原题边界 1000 随机
    for(int i = 0; i < 1000; ++i) reports[5].push_back(rng() % 1000);

    // Test 7: 原题边界 1000 全员到达打乱
    reports[6].resize(1000);
    iota(reports[6].begin(), reports[6].end(), 0);
    shuffle(reports[6].begin(), reports[6].end(), rng);

    // Test 8: TLE杀手 - 50000 随机
    for(int i = 0; i < 50000; ++i) reports[7].push_back(rng() % 50000);

    // Test 9: TLE杀手 - 100000 全员到达打乱
    reports[8].resize(100000);
    iota(reports[8].begin(), reports[8].end(), 0);
    shuffle(reports[8].begin(), reports[8].end(), rng);

    // Test 10: 终极恶心数据 - 100000 次全都报最后一个人的编号
    reports[9].assign(100000, 99999);

    // 开始生成文件
    for (int i = 0; i < 10; ++i) {
        int N = Ns[i];
        int M = Ms[i];
        
        // --- 1. 生成 .in 文件 ---
        string in_filename = to_string(i + 1) + ".in";
        ofstream fout_in(in_filename);
        if (!fout_in.is_open()) continue;
        
        fout_in << N << " " << M << "\n";
        for (int j = 0; j < M; ++j) {
            fout_in << reports[i][j] << (j == M - 1 ? "" : " ");
        }
        fout_in << "\n";
        fout_in.close();

        // --- 2. 调用 O(N+M) 标程计算正确答案 ---
        vector<int> ans = solve(N, M, reports[i]);

        // --- 3. 生成 .out 文件 ---
        string out_filename = to_string(i + 1) + ".out";
        ofstream fout_out(out_filename);
        if (!fout_out.is_open()) continue;
        
        if (ans.size() == 1 && ans[0] == -1) {
            fout_out << N << "\n"; // 全员到齐
        } else {
            for (int j = 0; j < ans.size(); ++j) {
                fout_out << ans[j] << (j == ans.size() - 1 ? "" : " ");
            }
            fout_out << "\n";
        }
        fout_out.close();

        cout << "成功生成 Test " << (i + 1) << "\t | N = " << N << "\t | M = " << M << "\n";
    }

    cout << "\n所有测试数据生成完毕！无递归防爆栈，10个测试点总文件大小约 1.5 MB。" << endl;
    return 0;
}

OJ 部署与防坑指南

1. 头文件保障：代码中包含了 <numeric>，这是用来调用 iota 函数的（它可以快速给数组填入 0, 1, 2... N-1），它是极度优雅且避免写大量 for 循环赋值的高效算法函数。配合 <algorithm> 里的 shuffle 使用，让数据生成器兼具高性能。
2. 避免文件体积爆炸（符合你的要求）：虽然 $100000$ 听起来是个巨大的数字，但在存储空间上，包含 10 万个整数加上空格文本文件，实际大小只有约 550 KB。所有的 .in 和 .out 加在一起大约在 $1.5 \text{ MB}$ 上下，读取与评测速度在 OJ 系统中只需几毫秒。
3. 彻底区分复杂度：把这套数据放到 OJ，设置 Time Limit 为 1000 ms（默认值）。你会惊喜地看到，使用数组直接映射（桶思想）的学生瞬间满分；而使用两层 for 循环遍历的学生，会在 Test 8, 9, 10 遭遇红色的 Time Limit Exceeded。你作为教练就能直接抓住这批同学，给他们讲授“哈希映射”的真谛了！

你好！很高兴带你把草稿纸上的“点名册”思路落实到严谨的代码中。

这道题其实是数据结构中**“哈希映射（Hash）”的最基础应用。在计算机科学中，如果你听到一个高频词叫“空间换时间”**，这道题就是最好的诠释。

为了让你体会到算法思维的进步，我会给你展示两个版本：一个是大部分没经过系统训练的初学者凭本能写出的“暴力查找”版，另一个是竞赛生必须掌握的“桶标记（哈希）”最优版。所有的代码均严格遵循 NOIP/CSP C++14 竞赛标准。

版本一：新手直觉版 —— 暴力遍历查找（时间换空间）

初学者的直觉通常是：“你给我什么，我就存什么”。把 $M$ 次报数存进一个大数组，然后对于班上的每一个编号，都去这个大数组里从头到尾找一遍。

#include <iostream>
#include <vector>

using namespace std;

int main() {
    // 优化系统 IO 速度，竞赛基本素养
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, m;
    if (!(cin >> n >> m)) return 0;

    // 用一个数组把 M 次报出的编号全记下来
    vector<int> records(m);
    for (int i = 0; i < m; ++i) {
        cin >> records[i];
    }

    vector<int> missing_students; // 用来存放缺席同学的编号

    // 外层循环：拿着点名册上的名字（从 0 到 n-1），挨个寻找
    for (int i = 0; i < n; ++i) {
        bool found = false;
        
        // 内层循环：在报数记录里从头到尾找，看看有没有 i
        for (int j = 0; j < m; ++j) {
            if (records[j] == i) {
                found = true;
                break; // 找到了就不用往后找了
            }
        }
        
        // 如果翻遍了记录都没找到，说明这名同学缺席
        if (!found) {
            missing_students.push_back(i);
        }
    }

    // 题目输出要求：如果全部到达（缺席名单为空），输出 n
    if (missing_students.empty()) {
        cout << n << "\n";
    } else {
        // 否则输出缺席的编号
        for (int i = 0; i < missing_students.size(); ++i) {
            cout << missing_students[i] << (i == missing_students.size() - 1 ? "" : " ");
        }
        cout << "\n";
    }

    return 0;
}

【复杂度分析与思考】

• 空间复杂度：$O(M)$。开辟了一个大小为 $M$ 的数组来存储每次报数。
• 时间复杂度：$O(N \times M)$。外层循环遍历 $N$ 个同学，内层循环最多遍历 $M$ 条记录。如果是最坏情况（所有人都不在），要执行 $N \times M$ 次判断。
• 优化思考：本题数据 $N, M \le 1000$，$1000 \times 1000 = 10^6$（一百万次），这个代码在考场上能过。但是，如果 $N, M$ 放大到 $10^5$，运算量就会达到 $10^{10}$，绝对会超时（TLE）！因为“在杂乱无章的记录里找一个人”太慢了。我们需要一种能“瞬间判定”的方法。

版本二：竞赛标答版 —— 桶标记/哈希法（空间换时间，强烈推荐！）

这就是我们在草稿纸上推演的方法：建立一本真正的“点名册”（一个大小为 $N$ 的布尔数组）。读入报数时，直接把数组对应下标的值修改为 true。

#include <iostream>
#include <vector>

using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, m;
    if (!(cin >> n >> m)) return 0;

    // 关键点1：开辟一本大小为 N 的“点名册”（桶），初始值全为 false（没来）
    // 数组下标 0~N-1 完美对应同学的编号！
    vector<bool> present(n, false);
    
    int present_count = 0; // （优化细节）顺手记录有几个【不重复】的人到了

    // 关键点2：边读入，边打勾
    for (int i = 0; i < m; ++i) {
        int x;
        cin >> x;
        // 如果这个编号是第一次被报到，我们让到达人数 +1
        if (!present[x]) {
            present[x] = true;  // 在点名册对应位置打勾！
            present_count++;
        }
        // 如果顽皮同学多次报数，此时 present[x] 已经是 true 了，不做任何操作（天然去重）
    }

    // 步骤 3：扫尾检查
    // 题目特判：如果到了的人数等于全班人数 n
    if (present_count == n) {
        cout << n << "\n";
    } else {
        // 否则，从头到尾扫一遍点名册
        bool first_output = true;
        for (int i = 0; i < n; ++i) {
            // 如果点名册上是 false，说明缺席
            if (!present[i]) {
                if (!first_output) cout << " ";
                cout << i;
                first_output = false;
            }
        }
        cout << "\n";
    }

    return 0;
}

【复杂度分析与优化建议】

• 空间复杂度：最优秀的 $O(N)$。我们创建了一个大小为 $N$ 的布尔数组（哪怕 $N=10^7$ 也只占不到 10MB 内存，极其轻量）。
• 时间复杂度：绝对的 $O(N + M)$。
  • 读取打勾循环执行 $M$ 次；
  • 最后扫描点名册循环执行 $N$ 次；
  • 没有任何嵌套循环！当 $N, M = 10^5$ 时，只需执行 $20$ 万次操作，比版本一快了五万倍以上！瞬间 AC。
• 教练点拨（为什么叫理论最优？）：因为你即使什么逻辑都不写，仅仅把题目的输入数据读进内存，就需要 $O(M)$ 的时间；要把所有缺席的同学排查出来，也必须至少过一遍全班同学 $O(N)$。所以 $O(N+M)$ 是物理上的理论极限，不可能有比它更快的算法了。

这就是**“以空间（数组下标）换取时间（嵌套搜索）”**的巅峰艺术。把版本二在脑海里多过几遍，它是你通往更高阶“桶排序”和“散列表查找”的一把钥匙！如果有不懂的细节，随时提问。

你好！很高兴能以教练的身份指导你。这是一道非常经典的**“哈希映射（Hash）思想与频率统计”**入门题。它非常贴近生活场景，能很好地训练你把现实问题转化为计算机数据结构的能力。

我们先把键盘推开，拿出草稿纸，一起来分析这道题。

1. 教练的思路提示（不提供完整代码）

• 提示一：老师的“点名册”。 现实中老师是怎么确认谁没来的？肯定是拿着一张印着所有同学名字（或学号）的花名册，听到谁喊了，就在谁的名字后面打个勾（√）。你能用什么数据结构在计算机里模拟这张“点名册”呢？
• 提示二：无视“顽皮的捣蛋鬼”。 题目说有同学会多次报出自己的编号。在你的点名册上，如果 0 号同学报了一次，你打了个 √；他又报了一次，你又在同一个地方打了个 √。其实不管打多少个勾，只要有勾，他就已经是“到了”。所以这其实是一个**去重（去干扰）**的过程。
• 提示三：扫尾检查。 等这 $M$ 次报数都结束了，你只需要从头到尾把点名册看一遍：
  • 如果发现有没有打勾的，就把他的编号抄下来。
  • 如果发现全打满勾了，说明所有人都到了，按照题目要求，直接输出总人数 $N$ 即可。

2. 预备知识点总结

要轻松拿下这道题，你需要掌握以下几个编程知识点：

1. 一维数组（Array）的应用：开辟一个大小为 $N$ 的数组，用作“点名册”。这种通过“值”直接找“位置（下标）”的思想，就是未来极为重要的**桶排序（Bucket Sort）和哈希表（Hash Table）**的雏形。
2. 布尔类型（bool）：数组的类型不需要是 int，因为我们只关心“来”或“没来”，用 bool 数组存放 true 或 false 是最优雅的。
3. 循环结构：一个 for 循环用于读取报数并“打勾”；另一个 for 循环用于最后扫描点名册寻找缺席者。
4. 计数器思想（可选但推荐）：用一个变量记录究竟有几个不重复的同学到了，方便最后一步判断是否“全员到齐”。

3. 启发式与图形式的草稿纸推导（教学模拟）

“来，草稿纸摊开，我们用样例 2 来模拟一下。$N=3$（班上有3人，编号 0,1,2），$M=5$（报了 5 次数：0 0 0 0 0）。”

第一步：建立点名册（初始化）

教练启发：“既然编号刚好是 $0$ 到 $N-1$，那我们可以直接用数组的下标代表学号！建一个大小为 3 的数组 present，一开始大家都没来，全填上 false (简写为 F)。”

[草稿纸推导] 点名册初始化
编号(下标 i):   0      1      2
是否到达(值):   [ F ]  [ F ]  [ F ]

第二步：处理报数（打勾）

教练启发：“现在开始依次读取这 5 次报数。每次读到一个数 $x$，我们就让 present[x] = true。”

第 1 次报数 0: present[0] = T  -> [ T, F, F ]
第 2 次报数 0: present[0] = T  -> [ T, F, F ]  (顽皮同学重复报数，状态不变)
...
第 5 次报数 0: present[0] = T  -> [ T, F, F ]

第三步：检查结果

教练启发：“报数结束！现在我们只需要按顺序遍历数组下标 0 到 N-1。”

检查 0: 是 T，跳过。
检查 1: 是 F！记录，没来！
检查 2: 是 F！记录，没来！
结果：缺席的是 1 和 2。输出 1 2。

第四步：复杂度的思考与优化建议

• 空间复杂度：
  • 我们需要一个大小为 $N$ 的数组来做点名册。
  • 分析结果：$N \le 1000$，1000 个布尔值占用仅仅 1KB 左右的内存，空间复杂度为最优秀的 $O(N)$。
• 时间复杂度：
  • 我们读入了 $M$ 个数字（执行 $M$ 次打勾）。
  • 然后我们扫描了数组的 $N$ 个位置。
  • 分析结果：总操作次数是 $M + N$。即时间复杂度为 $O(N + M)$。考虑到 $M, N \le 1000$，程序只会运行约 2000 次操作。这不仅是完美的，而且是计算机处理此类问题的理论极限速度（因为你无论如何都要把输入读完）。
• 代码逻辑优化建议：
  • 如何快速判断是否全员到齐？可以在遇到把 F 变成 T 时，让一个“到达总人数”的计数器 +1。扫描结束后，如果 到达总人数 == N，就直接输出 $N$ 结束程序，不用再费劲去检查谁没来了。

4. 读题时的“题眼”（关键词）提取技巧

做这道题，在读题时必须立刻锁定以下几个关键词，它们是帮你免除 Bug 的护身符：

1. “编号从 $0$ 到 $N-1$” —— 题眼：数组下标的完美映射。 C++ 数组的下标恰好就是从 0 开始的。这明示了你直接用 arr[x] = true 来记录即可，不需要任何诸如 x-1 或 x+1 的下标换算。
2. “多次报出” —— 题眼：去重。 如果你试图用一个巨大的数组把所有报出来的数存下来再慢慢处理，不仅浪费空间还容易绕晕。点名册“覆盖赋值”的思想（多次赋值 true 结果还是 true）天然解决了去重问题。
3. “如果所有同学都到达，则输出 $N$” —— 题眼：特判输出要求。 不要一激动看到没有缺席者就不输出任何东西结束了，题目要求这种情况下要输出一个数字 $N$。
4. “由小到大输出” —— 题眼：隐藏的排序福利。 由于我们是用 0 到 N-1 的数组下标记录的，当你用 for (int i = 0; i < n; ++i) 从头到尾遍历点名册去寻找 false 时，输出的顺序天然就是从小到大的，根本不需要你再去写排序算法（如冒泡排序、sort 函数等）。

思路已经很清晰了。现在你可以拿好这本“点名册”（数组），尝试把代码敲出来了！如果有卡壳的地方，随时叫我。