sort：排序和自定义比较器

// STL 专题 · sort —— 默认升序、降序、只排一部分
//
// ★ 这一份只练 `sort` 的三种最常用写法，全是**不带比较器**的那种：
//     sort(a.begin(), a.end());                              升序
//     sort(a.begin(), a.end(), greater<int>());              降序
//     sort(a.begin() + l, a.begin() + r);                    只排 [l, r) 这一段
//
// ⚠ 输入第一行 n，第二行 n 个整数。

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

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

  int n;
  cin >> n;
  vector<int> a(n);
  for (int &x : a) cin >> x;

  cout << "原来： ";
  for (int x : a) cout << x << ' ';
  cout << "\n\n";

  // ① 升序
  vector<int> b = a;
  sort(b.begin(), b.end());
  cout << "① sort(b.begin(), b.end())               ";
  for (int x : b) cout << x << ' ';
  cout << '\n';

  // ② 降序：greater<int>() 就是「反过来比」
  vector<int> c = a;
  sort(c.begin(), c.end(), greater<int>());
  cout << "② sort(c.begin(), c.end(), greater<int>()) ";
  for (int x : c) cout << x << ' ';
  cout << '\n';

  // ③ 只排一段：[l, r) 左闭右开。
  //    ⚠ 第二个参数是 **l + 1**，不是 l —— 因为它是「尾后位置」。
  //    这一段排完，l 前面的和 r 后面的都不动。
  vector<int> d = a;
  int l = 1, r = 4;
  sort(d.begin() + l, d.begin() + r);
  cout << "③ 只排 [" << l << ", " << r << ") 这一段        ";
  for (int i = 0; i < n; i++) {
    if (i == l) cout << "| ";
    cout << d[i] << ' ';
    if (i == r - 1) cout << "| ";
  }
  cout << '\n';
  cout << "   ↑ | 之间的才是被排过的，外面两个都没动\n";

  return 0;
}

// STL 专题 · sort —— 打包成 pair 一起排
//
// 这是 OI 里用得最多的 sort 写法：**把要一起走的东西打包成一个元素，再排。**
//
// 题目：给 n 个学生（学号 + 分数），按分数从高到低输出学号；分数相同则学号小的在前。
//
// ★ 为什么要打包：`sort` 搬的是**你给它的那些元素本身**。
//   你只把分数交了进去，它就只搬分数 —— 不会帮你把学号一起搬。
//
// ⚠ 输入第一行 n，之后 n 行每行是 `学号 分数`。

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

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

  int n;
  cin >> n;

  // ★ 全部内容就这两句：打包成 {分数, 学号}，然后排。
  vector<pair<int, int>> v;              // {分数, 学号}
  for (int i = 0; i < n; i++) {
    int id, score;
    cin >> id >> score;
    v.push_back({score, id});
  }

  // 分数降序；分数相同时学号小的在前。
  // ⚠ 两个关键字的方向不一样，所以要手写，不能直接用 greater<pair>() ——
  //   那个是**两个关键字一起反**，会把第二级也变成降序。
  sort(v.begin(), v.end(), [](const pair<int, int>& a, const pair<int, int>& b) {
    if (a.first != b.first) return a.first > b.first;   // 分数降序
    return a.second < b.second;                         // 学号升序
  });

  cout << "排好之后（分数 学号）：\n";
  for (const auto& p : v) cout << setw(4) << p.first << ' ' << p.second << '\n';

  cout << "\n按题目要求输出学号：\n";
  for (const auto& p : v) cout << p.second << ' ';
  cout << '\n';
  return 0;
}