ZeroJudge 解題筆記：o626.檔案順序 (Files)

作者：王一哲
日期：2026年10月16日


ZeroJudge 題目連結：o626.檔案順序 (Files)

題目 pdf 檔連結：檔案順序 (Files)

解題想法

這題是TOI練習賽202409潛力組第1題，這題跟同組題目的第2題〈o627.校外教學分組 (Trip)〉都很難，第3題〈o628.天秤 (Libra)〉比較簡單。題目是多組測資。每組測資第1列為2個整數 $n (1 \leq n \leq 2 \times 10^5)$、$k (1 \leq k \leq 2 \times 10^5)$，分別代表有 $n$ 個檔案、$k$ 次操作。接下來 $n$ 列，每列有 4 個整數，分別代表檔案的名稱、修改時間、類型、大小。最後一列有 $k$ 個 1 到 4 的數字，分別代表用檔案的名稱、修改時間、類型、大小作為排序依據。如果有多個檔案這個屬性的值相同，則這幾個檔案保持前一次排序後的順序，也就是用 stable sort。

如果前一次操作與這次操作用的屬性不同，則這次操作為升序排序 （ascending order)，也就是由小到大排序；如果重複點同樣的屬性第二次，會改成降序排序 （descending order)，也就是由大到小排序。這點在解題時特別重要，因為 $n, k$ 的數值極大，如果真的模擬每一次的排序過程絕對會超時。但由於這個操作上的特性，我們可以用一個串列 $ops$ 記錄操作的索引值 $idx$ 以及目前為升序 (1) 或降序 (-1) 排列，如果連續使用相同的屬性排序，只要更新升序或降序即可；如果用不同屬性排序，於 $ops$ 最後面接上 $[idx, 1]$。

另一個要利用的特性是操作過程中如果先用了某個屬性排序，再用另一個屬性排序，之後再回來用前面用過的屬性排序，只有最後面這次的排序有效。例如先用名稱，再用修改時間，之後再回來用名稱排序，則第一次排序的效果會被後面同樣用名稱排序的效果蓋掉。因此，我們可以倒序讀取 $ops$，取出用這 4 個屬性排序的索引值及升序、降序，資料存入串列 sort_key。將 sort_key 組成 tuple，只排序一次，將排序後的檔案依序輸出。

不過這題的記憶體限制極小，只有 64 MB，我用 Python 解題最多只能通過 50% 的測資就遇到 MemoryError，目前看排行還沒有人用 Python 過關。用 C++ 則是 0.2 s、9.4 MB 過關。

Python 程式碼

只能通過 40% 的測資。

def solve():
    import sys

    result = []
    data = sys.stdin.read().split()
    ptr = 0
    while ptr < len(data):
        n = int(data[ptr])
        k = int(data[ptr + 1])
        ptr += 2
        files = []  # (name, time, type, size)
        for _ in range(n):
            file = tuple(map(int, data[ptr : ptr + 4]))
            ptr += 4
            files.append(file)
        
        operations = []  # idx of operation
        state = [0] * 5  # 1 ascending, -1 descending, 0 none
        for _ in range(k):
            idx = int(data[ptr])
            ptr += 1
            operations.append(idx)
            if state[idx] == 0:
                state[idx] = 1
            else:
                state[idx] *= -1
        
        sort_key = []  # (idx, 1 or -1)
        used = [False] * 5
        for idx in operations[::-1]:
            if not used[idx]:
                used[idx] = True
                sort_key.append((idx, state[idx]))
        
        def mykey(file):
            return tuple(file[idx - 1] * val for idx, val in sort_key)
        
        files.sort(key = mykey)
        
        for file in files:
            res = " ".join(map(str, file)) + "\n"
            result.append(res)
        
    # 輸出答案
    sys.stdout.write("".join(result))

if __name__ == "__main__":
    solve()

只能通過 50% 的測資。

def solve():
    import sys

    def get_tokens():
        for line in sys.stdin:
            for part in line.split():
                yield int(part)

    data = get_tokens()

    while True:
        try:
            n = next(data)  # 檔案數量
        except StopIteration:
            break
        
        k = next(data)  # 操作次數
        
        # 讀取 n 個檔案資料
        files = [(next(data), next(data), next(data), next(data)) for _ in range(n)]
        
        # 讀取 k 次操作，如果是連續相同的操作，將升序 1、降序 -11 反過來
        ops = []  # (操作種類, 1 或 -1)
        for _ in range(k):
            idx = next(data)
            if not ops or ops[-1][0] != idx:  # 如果 ops 是空的或是 ops 最後一項不是 idx
                ops.append([idx, 1])  # 新的操作種類，預設為升序 1
            else:  # 相同的操作，交換 +1 -1
                ops[-1][1] *= (-1)

        # 倒序讀取 ops，找出有效的操作，最多 4 種
        sort_key = []  # 有用的操作
        used = [False] * 5  # 已經使用過的操作種類
        for idx, val in ops[::-1]:
            if used[idx]: continue
            used[idx] = True
            sort_key.append((idx, val))
            if len(sort_key) == 4: break

        # 自訂排序用的 tuple
        def mykey(file):  # 需要引入參數 file
            return tuple(file[idx - 1] * val for idx, val in sort_key)
        
        # Python 的 sort 為穩定排序，如果這次排序的比較值相同，會按照前一次的順序
        files.sort(key = mykey)

        # 輸出檔案內容
        for file in files:
            res = " ".join(map(str, file))
            sys.stdout.write(f"{res}\n")

if __name__ == "__main__":
    solve()

C++ 程式碼

使用時間約為 0.2 s，記憶體約為 9.6 MB，通過測試。

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

struct File {
    int arr[4];  // 名稱，時間，種類，大小
};

int main() {
    ios::sync_with_stdio(0); cin.tie(0);
    int n, k;  // 檔案數量，操作次數
    while(cin >> n >> k) {
        // 讀取 n 個檔案資料
        vector<File> files (n);
        for(int i = 0; i < n; i++) {
            cin >> files[i].arr[0] >> files[i].arr[1] >> files[i].arr[2] >> files[i].arr[3];
        }
        
        // 讀取 k 次操作，如果是連續相同的操作，將升序 1、降序 -1 反過來
        vector<pair<int, int>> ops;  // {操作種類, 1 或 -1}
        for(int i = 0; i < k; i++) {
            int idx;
            cin >> idx;
            if (ops.empty() || ops.back().first != idx) {  // 如果 ops 是空的或是 ops 最後一項不是 idx
                ops.push_back({idx, 1});  // 新的操作種類，預設為升序 1
            } else {  // 相同的操作，交換 +1 -1
                ops.back().second *= (-1);
            }
        }

        // 倒序讀取 ops，找出有效的操作，最多 4 種
        vector<pair<int, int>> sort_key;  // 有用的操作
        vector<bool> used (5, false);  // 已經使用過的操作種類
        for(auto it = ops.crbegin(); it != ops.crend(); it++) {
            if (used[(*it).first]) continue;
            used[(*it).first] = true;
            sort_key.push_back(*it);
            if (sort_key.size() == 4) break;
        }

        // 使用 lambda function 自訂排序用的比較式
        auto mycmp = [&] (const File& a, const File& b) {
            for(auto& it : sort_key) {
                int idx = it.first - 1, val = it.second;
                if (a.arr[idx] != b.arr[idx]) {
                    if (val == 1) {  // 升序
                        return a.arr[idx] < b.arr[idx];
                    } else {  // 降序
                        return a.arr[idx] > b.arr[idx];
                    }
                }
            }
            return false;  // 所有的 sort_key 項目皆相等，回傳 false
        };

        // 使用 stable_sort，如果這次排序的比較值相同，會按照前一次的順序
        stable_sort(files.begin(), files.end(), mycmp);

        // 輸出檔案內容
        for(auto file : files) {
            cout << file.arr[0] << " " << file.arr[1] << " " << file.arr[2] << " " << file.arr[3] << "\n";
        }
    }
    return 0;
}