Solution

Ta có thuật toán tham lam sau:

• Ở mỗi lượt, lần lượt từ học sinh ~1~ tới học sinh ~n~ lấy viên kẹo ngon nhất đối với học sinh đó trong túi kẹo ~U~.
• Lặp lại cho đến khi túi kẹo ~U~ rỗng.

Rõ ràng thuật toán này thỏa mãn điều kiện 1 và 2. Ta kiểm tra điều kiện thứ 3. Với học sinh ~i~ và học sinh ~j \ne i~:

• Nếu ~i < j~ thì ở mỗi lượt học sinh ~i~ được lấy kẹo trước. Giả sử ở mỗi lượt ~i~ lấy viên kẹo ~x~ và ~j~ lấy viên kẹo ~y~. Vì ~i~ được đi trước ~j~ ở mỗi lượt và ~i~ luôn lấy viên kẹo ngon nhất, ta có ~v_i(x) \ge v_i(y)~. Cộng lại tất cả các viên kẹo của ~i~ và ~j~ ta có ~v_i(S_i) \ge v_i(S_y)~.
• Nếu ~i > j~, ta có thể nhìn thuật toán trên dưới góc: học sinh ~1~ tới ~j~ lấy một viên kẹo, rồi một lượt chính thức bắt đầu từ ~j + 1~, đi tới học sinh ~n~, vòng về học sinh ~1~ rồi đi tới học sinh ~j~, dưới dạng mảng thì nhìn như thế này ~[1, 2, \dots, n], [1, 2, \dots, n], \dots \rightarrow [1, 2, \dots, j], [j + 1, \dots, n, 1, \dots, j], [j + 1, \dots, n, 1, \dots, j], \dots~ Vì thế, ngoại trừ viên kẹo đầu tiên ~j~ lấy (gọi là ~\hat{j}~), ở mỗi lượt sau ta đều có ~v_i(x) \ge v_i(y)~, nên là ~v_i(S_i) \ge v_i(S_j) - v_i(\hat{j}) \ge v_i(S_j) - \max_{k \in S_j} v_i(k)~.

Ta có thể cài đặt bằng cách sắp xếp dãy kẹo cho mọi học sinh, rồi thực hiện thuật toán trên bằng cách sử dụng một con trỏ cho mỗi học sinh.

Độ phức tạp là ~O(nm \log nm)~.

Code mẫu

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

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, m; cin >> n >> m;
    vector c(n, vector<int>(m));
    vector ind(n, vector<int>(m));
    vector<int> pt(n);
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            cin >> c[i][j];
            ind[i][j] = j;
        }
        sort(ind[i].begin(), ind[i].end(), [&](int u, int v) {
            return c[i][u] > c[i][v];
        });
    }
    vector<bool> ok(m);
    vector ans(n, vector<int>());
    for (int i = 0; i < m; i++) {
        int x = i % n; // current student
        while (ok[ind[x][pt[x]]]) {
            pt[x]++;
        }
        ok[ind[x][pt[x]]] = true;
        ans[x].push_back(ind[x][pt[x]]);
    }
    for (int i = 0; i < n; i++) {
        cout << ans[i].size();
        for (int v : ans[i]) {
            cout << " " << v + 1;
        }
        cout << '\n';
    }
}