该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

【C++语言：排序与结构体】基础排序与多关键字排序

【学习目标】熟练掌握代码并在合理时间内运行正确、提交正确。

学习内容：
1、掌握使用 std::sort 对大规模一维数组进行高效排序（$O(N \log N)$）；
2、掌握使用结构体（struct） 封装复杂数据；
3、掌握编写自定义比较函数（cmp），实现清晰的多关键字（优先级）排序逻辑；
4、理解 $10^6$ 级别数据量下的输入输出效率要求。

【题意】

任务一：给出 $N$ 个整数 $a_i$，要求将它们从小到大排序后输出。

任务二：给出 $M$ 个整数三元组，每个三元组包含编号 $i$（从 $1$ 到 $M$）以及两个整数 $b_i, c_i$。要求对这 $M$ 个三元组按以下规则排序，并输出排序后的编号序列：

1. 先按 $b_i + c_i$ 的值从小到大排序；
2. 若 $b_i + c_i$ 相同，再按 $c_i$ 的值从小到大排序；
3. 若再相同，则按编号 $i$ 从小到大排序。

【输入格式】

第一行输入一个整数 $N$。

第二行输入 $N$ 个整数，表示任务一的 $a_i$，中间用空格隔开。

第三行输入一个整数 $M$。

接下来 $M$ 行，每行输入两个整数 $b_i, c_i$，表示第 $i$ 个三元组的值（$i$ 从 $1$ 开始递增）。

数据范围：$1 \le N, M \le 10^6$，$1 \le a_i, b_i, c_i \le 10^6$。

【输出格式】

第一行输出任务一排序后的 $N$ 个数，两数之间用空格隔开。

第二行输出任务二排序后的 $M$ 个三元组编号，两数之间用空格隔开。

3
3 1 2
3
2 3
1 4
3 2

1 2 3
3 1 2

样例解释：

任务二中，3个三元组的 (b+c, c, id) 分别为 (5, 3, 1), (5, 4, 2), (5, 2, 3)。按规则排序后，c 最小的排在前面，因此顺序为 id=3, id=1, id=2)*

💡 小贴士（供参考）：

1. 时间复杂度与 TLE 警告： 本题数据规模达到 $10^6$。如果学生使用冒泡排序、选择排序或插入排序（$O(N^2)$），运算次数将达到 $10^{12}$，必定超时（TLE）。必须强调使用 C++ 标准库的 std::sort，其时间复杂度为 $O(N \log N)$，可以在 0.1 秒内轻松处理 $10^6$ 的数据。

2. 输入输出加速（必考点）： 当输入输出数据量达到百万级别时，普通的 cin 和 cout 可能会因为同步机制导致超时。必须要求学生在 main 函数开头加入输入输出加速代码：

   ios::sync_with_stdio(0);
   cin.tie(0);
   

   或者坚持使用 scanf 和 printf。

3. 多关键字排序的清晰逻辑： 引导学生写出层次分明的 cmp 函数。不要试图用一行复杂的逻辑运算符写完，清晰的 if-else 不仅不易出错，而且编译器优化后效率一样高：

4. 数据范围的巧思： 题目特别注明了 $b_i, c_i \le 10^6$，这意味着 $b_i + c_i \le 2 \times 10^6$，完全在 32 位 int 的安全范围内（int 最大约 $2 \times 10^9$）。这可以放心使用 int。