Algorithm Notebook 2 — Sorting Stu Records: Three Eras of C++

Luogu P1093 — Scholarship

link: https://www.luogu.com.cn/problem/P1093

1. Problem Statement

There are $n$ Stus, each with three exam scores: Chinese (ch), Math (math), and English (eng). The task is to rank them by the following criteria:

1. Total score — descending (higher is better);
2. Chinese score — descending (tiebreaker for equal totals);
3. Stu ID — ascending (final tiebreaker: smaller ID first).

Output the ID and total score of the top $5$ Stus.

Trivial — $n \le 300$, any algorithm passes. But I’m not here to talk about complexity. I want to talk about three pieces of code that solve exactly the same problem, written roughly 15 years apart, and what the differences between them tell us about what it even means to code in an era where AI writes faster than we type.

2. A Bit of History: The STL Ban (Pre-2011)

Before we look at the code, here’s something most people outside the Chinese OI scene don’t know.

CCF banned the use of STL in NOIP before 2011. The official reasoning: std::sort and std::vector hid too much — if you used them, you didn’t “really understand.” I remember my coach: “You can’t use sort. Write your own quick sort. How else will you learn?”

The ban lifted in 2011. Overnight, std::sort, std::vector, std::string, std::priority_queue became legal. A generation of OIers who’d memorized quick sort by heart could finally breathe.

The three code samples below span this divide.

3. Version A: Hand-Written Quick Sort (Pre-2011)

This is the code I grew up typing. No STL. No std::vector. Everything from scratch.

#include<cstdio>
#include<iostream>
using namespace std;
const int MAXN = 300 + 5;
struct Stu{
    int ch, math, eng, total, num;
    const bool operator<(const Stu &other){
        if (total != other.total) return total < other.total;
        else if (ch != other.ch) return ch < other.ch;
        else return num > other.num;
    }
};
Stu stu[MAXN];
void quick_sort(int l, int r){
    if (l >= r) return;
    Stu pivot = stu[(l + r) >> 1];
    int i = l - 1, j = r + 1;
    while (i < j){
        do i++; while(stu[i] < pivot);
        do j--; while(pivot < stu[j]);
        if (i < j) {
            Stu t = stu[i]; stu[i] = stu[j]; stu[j] = t;
        }
    }
    quick_sort(l, j);
    quick_sort(j + 1, r);
}
int main(){
    int n; cin >> n;
    for (int i = 1; i <= n; i++){
        cin >> stu[i].ch >> stu[i].math >> stu[i].eng;
        stu[i].total = stu[i].ch + stu[i].math + stu[i].eng;
        stu[i].num = i;
    }
    quick_sort (1, n);
    for (int i = n; i > n - 5; i--){
        Stu x = stu[i];
        cout << x.num << " " << x.total << endl;
    }
}

There’s a lot going on in this code, but I’ll point out just three things.

First, the hand-written quick sort — Hoare partition, pivot cached before swapping, recursion on (l, j) and (j+1, r). Each of these choices was something you got wrong at least once. The pivot-cache bug alone has probably wasted collectively years of debugging across Chinese OI training rooms.

Second, the inverted comparator logic. The problem wants descending totals, but quick sort builds ascending order. So smaller totals go first, and then you iterate backwards from the end. The num > other.num to get smaller IDs at the front — that inversion only makes sense when you remember you’re printing in reverse. If this reads like solving a puzzle, that’s because it is. Every contestant spent mental energy on this inversion that could have gone to something else.

4. Version B: std::sort Arrives (Post-2011)

CCF lifts the ban. std::sort is legal. The sorting burden vanishes. What happens to the rest?

#include<iostream>
#include<algorithm>
using namespace std;
struct Stu{
    int ch, math, eng, total, num;
    bool operator < (const Stu & other){
        if (total != other.total) return total < other.total;
        else if (ch != other.ch) return ch < other.ch;
        else return num > other.num ;
    }
};
const int MAXN = 300 + 5;
Stu stu[MAXN];
int main (){
    int n; cin >> n;
    for (int i = 1; i <= n; i++){
        int ch, math, eng;
        cin >> ch >> math >> eng;
        stu[i].ch = ch, stu[i].math = math, stu[i].eng = eng, stu[i].total = ch + math + eng, stu[i].num = i;
    }
    sort (stu + 1, stu + n + 1);
    for (int i = n; i > n - 5; i--){
        auto x = stu[i];
        cout << x.num << " " << x.total;
        if (i > n - 5) cout << endl;
    }
    return 0;
}

The big change is obvious: ~15 lines of quick sort hidden behind a single call to sort(stu + 1, stu + n + 1). Introsort under the hood — $O(n \log n)$ guaranteed, no pivot bugs, no recursion anxiety.

I think this is the most honest version of the three. It captures a real moment: a community that had been told for years “you must build everything yourself” suddenly got permission to use the library, but didn’t yet know what else could change. The STL ban ended in 2011; the aesthetic of hand-rolled-everything took another decade to loosen its grip. New tools don’t automatically give you new habits. Those are transmitted person to person — coach to Stu, senior to junior — and they lag behind policy by years.

5. Version C: Modern C++

If I write this today, without contest pressure or historical weight:

#include <iostream>
#include <vector>
#include <algorithm>
#include <tuple>
using namespace std;

struct Stu {
    int id, ch, math, eng, total;
};

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

    int n;
    cin >> n;
    vector<Stu> stu(n);

    for (int i = 1; i <= n; ++i) {
        auto& s = stu[i];
        cin >> s.ch >> s.math >> s.eng;
        s.total = s.ch + s.math + s.eng;
        s.id = i;
    }

    sort(stu.begin(), stu.end(), [](const auto& x, const auto& y) {
        return tie(y.total, y.ch, x.id) < tie(x.total, x.ch, y.id);
    });

    for (int i = 0; i < 5; ++i)
        cout << stu[i].id << ' ' << stu[i].total << '\n';
}

And if you want to see where the language is headed (C++20):

#include <iostream>
#include <vector>
#include <algorithm>
#include <ranges>
#include <tuple>
using namespace std;

struct Stu {
    int id, ch, math, eng, total;

    auto operator<=>(const Stu& other) const {
        return tie(-total, -ch, id) <=> tie(-other.total, -other.ch, other.id); // The modern style
    }
};

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

    int n;
    cin >> n;
    vector<Stu> a(n);

    for (int i = 0; i < n; ++i) {
        auto& s = a[i];
        cin >> s.ch >> s.math >> s.eng;
        s.total = s.ch + s.math + s.eng;
        s.id = i + 1;
    }

    ranges::sort(a);

    for (const auto& s : a | views::reverse | views::take(5))
        cout << s.id << ' ' << s.total << '\n';
}

Look at the comparator in the C++17 version: tie(y.total, y.ch, x.id) < tie(x.total, x.ch, y.id). That one line says exactly what the problem asks: “rank by total descending, then Chinese descending, then ID ascending.” No mental inversion. No puzzle-solving. The direction is encoded in which side of the < each field sits on. I didn’t invent this trick — I saw it in someone else’s code and it stuck — but the point isn’t the trick. The point is that the code now reads like the problem statement.

The C++20 version goes further: views::reverse | views::take(5) says “from the back, take five.” ranges::sort(a) says “sort the whole thing.” The code is the spec. There’s nothing to decode.

And the smaller things: vector means no guessing MAXN. ios::sync_with_stdio(false) is automatic now — roughly 10× on input-heavy problems, zero cognitive cost. Everything 0-based, so no +1/-1 arithmetic in your head.

6. Side by Side

7. Debugging Chronicle (What Goes Wrong)

Meta-cognitive takeaway: The hardest bugs in Versions A and B aren’t in the sorting algorithm. They’re in the comparator — the part where you, a human, translate “descending total, descending Chinese, ascending ID” into a chain of if-else and boolean inversions. tie eliminates that translation step entirely. The direction lives in the value, not in the operator. That’s not syntax sugar — that’s removing an entire class of errors.

8. What Twenty Years Taught Me — And What AI Changes

flowchart LR
    A["Pre-2011<br/>Hand-write everything<br/>STL banned"] --> B["Post-2011<br/>std::sort allowed<br/>Old habits persist"]
    B --> C["C++17<br/>tie, lambda, vector<br/>Say what you mean"]
    C --> D["C++20<br/>ranges, spaceship<br/>The code is the spec"]
    D --> E["AI era<br/>Code as intent<br/>Human as architect"]

And perhaps this is the larger pattern behind every technological transition.

For most programmers, writing code has always been about turning ideas into executable instructions. In the early days, that meant implementing everything yourself: sorting algorithms, memory management, data structures. You needed to know how the machine worked because there were few layers between your intention and the hardware.

Then came the era of abstraction. We stopped rewriting quick sort and started calling std::sort. We stopped managing memory manually and started relying on containers and libraries. The skill was no longer just knowing how to build every component from scratch, but knowing which components already existed, how they worked, and when to trust them.

AI represents the next step of the same evolution.

This is not the first time humanity has automated a form of intellectual labor. In the early twentieth century, complex scientific calculations — including the calculations required for projects like nuclear physics — were often performed by teams of human “computers.” They performed enormous amounts of repetitive arithmetic by hand. But as problems grew beyond human capacity, machines like ENIAC emerged to take over the mechanical computation. The existence of computers did not make mathematics less important. It changed what mattered: from performing calculations to designing models, choosing methods, and understanding results.

AI coding tools are creating a similar transition.

The important shift is not that knowing Hoare’s partition scheme has become useless. Just as mathematicians still learn arithmetic, programmers still need to understand algorithms, data structures, and the principles behind the abstractions they use. The difference is where we place our attention.

Previously, programming often focused on: Why do I need to write this? How do I implement it correctly?

Today, increasingly, the important questions become: What is this code actually doing? Why was this approach chosen? How does it affect the entire system? How can it be improved? Is this the right abstraction? Does this design have elegance and clarity?

The bottleneck is moving from code production to code judgment.

For decades, the industry needed large numbers of programmers who could translate specifications into working code — much like organizations once needed large numbers of human calculators. AI will increasingly handle more of that mechanical translation. What becomes scarce are engineers who can recognize a flawed solution, design a clean architecture, understand trade-offs, and create software with taste.

The future programmer is not a faster typist. They are closer to an architect, a critic, and an artist: someone who understands the machine deeply enough to guide it, and understands the problem deeply enough to know what should be built.

The goal was never to become a human compiler.

The goal was always to become a human who understands. And that is what no mere matrix calculator can ever replace.