[入门赛 #7] 打 ACM 最快乐的就是滚榜读队名了 (Hard Version) 的题解

记住只在没有思路时使用题解，不要从它复制粘贴代码。请尊重题目和题解的作者。
在解题之前提交题解的代码会导致封禁。

作者： admin

概述

本题要求模拟一场 ICPC 比赛封榜后的滚榜过程，依次输出滚榜嘉宾念到的所有队名。关键在于把每支队伍的名次压成一个可比较的排名键，用有序容器维护还没滚完的队伍，并利用「只有名次上升才会换人」这一规则，让每条待判题至多被揭晓一次。

分析

核心观察

封榜后的提交在揭晓之前不影响任何东西，所以任意时刻的排名都由已经结算的提交唯一确定；而通过题数与罚时相同的队伍再由「首次出现在提交记录中的编号」区分，编号唯一，因此任意两支队伍的先后都是确定的，排名键构成全序。滚榜过程中，一支队伍只有在优于场上当前最后一名时才会被重新念到，而每一次名次上升都必然要消耗至少一条待判题，所以每条待判题至多参与一次排名变化。

思路

罚时只在题目通过的时候结算。若某队在时刻 $t$ ~t~（秒）通过了某题，且在此之前它对该题有过 $f$ ~f~ 次未通过的提交，则该题对罚时的贡献为

$\displaystyle \left\lfloor \frac{t}{60} \right\rfloor + 20 \times f$

分钟。没有通过的题目一律不计罚时；某题通过之后，该队对这一题的提交无论结果如何都不再产生任何影响。

按封榜时刻 $14400$ ~14400~ 秒（即 $4:00:00$ ~4:00:00~）切分提交记录：不晚于它的提交直接结算进通过题数与罚时，晚于它的提交（比赛最后一小时， $4:00:01 \sim 5:00:00$ ~4:00:01 \sim 5:00:00~）先记成待判题。待判题必须按题号从 A 开始升序揭晓，同一题内按提交时间升序；输入保证提交时间不降序，于是对每支队伍按题号做一次稳定排序即可。

排名键取 $(\text{ac}, \text{penalty}, \text{id})$ ：通过题数越大越靠前，通过题数相同时罚时越小越靠前，两者都相同时首次出现的编号越小越靠前。编号唯一，所以这个键是全序，任意两支队伍都能分出先后。把所有还没滚完的队伍放进一个按该键排序的有序集合，集合的首元素是第一名，末元素就是当前的最后一名。

滚榜的每一轮都从末元素开始：先念出它的队名并把它从集合中删除。若集合已经为空，说明刚念完的就是第一名，滚榜结束。若它已经没有待判题可以揭晓，直接换上一名。否则记下删除后集合的末元素 $W$ ~W~（场上新的最后一名），把该队的待判题逐条揭晓：只要某条揭晓后该队优于 $W$ ~W~，就说明它的名次上升，立刻按新的键把它插回集合并转去念 $W$ ~W~；若所有待判题揭晓完仍不优于 $W$ ~W~，说明它已经坐稳最后一名，不再插回。揭晓期间集合不会发生变化，所以 $W$ ~W~ 始终是场上的最后一名，用它作为比较对象是正确的。

若每揭晓一条提交就把全体队伍重排一次，单次是 $O(m \log m)$ ~O(m \log m)~，而揭晓总次数可达 $K$ ~K~，总复杂度 $O(K m \log m)$ ~O(K m \log m)~，这在 Easy Version 的范围内还可以接受，但本题 $m \le 2 \times 10^5$ ~m \le 2 \times 10^5~、 $K \le 2 \times 10^6$ ~K \le 2 \times 10^6~，整体重排必然超时。本题（洛谷 $P8890$ ~P8890~）与 Easy Version $B3692$ ~B3692~ 的题意完全相同，区别只在 $m$ ~m~ 与 $K$ ~K~ 的范围：Hard 版要求每一步都只在有序容器上做 $O(\log m)$ ~O(\log m)~ 的插入与删除，而不是重新算一遍全体名次。

具体示例

以题面样例（ $n = 2$ ~n = 2~， $m = 2$ ~m = 2~， $K = 4$ ~K = 4~）为例。封榜前队伍 abc 在 $0:00:01$ ~0:00:01~ 交 A 题未通过、在 $0:00:02$ ~0:00:02~ 通过 A 题，罚时为 $1 \times 20 + 0 = 20$ ~1 \times 20 + 0 = 20~ 分钟；队伍 bcd 在 $0:19:38$ ~0:19:38~ 通过 A 题，罚时为 $19$ ~19~ 分钟。此时两队都是 $1$ ~1~ 题，abc 罚时更大，排名靠后。封榜后 abc 在 $4:18:22$ ~4:18:22~ 又通过了 B 题，这条提交先记为待判题。

滚榜过程如下。

末元素是 abc（ $1$ ~1~ 题、 $20$ ~20~ 分钟），念出 abc。揭晓它的待判题：B 题通过，abc 变为 $2$ ~2~ 题，罚时为 $20 + \lfloor 15502 / 60 \rfloor = 20 + 258 = 278$ 分钟，优于此时场上最后一名 bcd，于是它被插回集合。
末元素是 bcd，念出 bcd。它没有待判题，直接换上一名。
末元素是 abc，念出 abc。集合已空，它是第一名，滚榜结束。

因此依次输出 $3$ ~3~ 行：abc、bcd、abc。

算法步骤

读入 n、m、K。
逐条读入提交记录，解析出提交时刻 t（秒）、题号 prob（A 记为 $0$ ~0~）、队名 name 和评测结果是否通过 ac；队名第一次出现时分配唯一编号 id 并新建一支队伍。
若 t 不大于 $14400$ ~14400~：该题已在 solved 中标记则跳过；否则通过时把 fails 中记录的失败次数折算成 $20$ ~20~ 分钟再加上 $t / 60$ ~t / 60~ 累加进 penalty，把通过题数 ac 加 $1$ ~1~ 并在 solved 中标记该题，未通过时把 fails 加 $1$ ~1~。若 t 大于 $14400$ ~14400~，把这条提交追加进该队的 pending。
对每支队伍，把 pending 按题号升序做一次稳定排序，同题内保持提交时间顺序。
按排名键把每支队伍插入有序集合 board，集合按 (通过题数降序, 罚时升序, 编号升序) 排列。
只要 board 非空就循环：取末元素（最后一名），输出它的队名并从 board 中删除；若 board 已经为空则结束；若它的 pending 已经揭晓完则进入下一轮；否则令 worst 为此时 board 的末元素，顺序揭晓 pending 中的提交（已通过的题跳过，通过时按第 $3$ ~3~ 步结算，未通过时累加 fails），一旦该队优于 worst 就把新的排名键插回 board 并进入下一轮，揭晓完仍不优于 worst 就不再插回。
按顺序输出所有念到的队名。

复杂度分析

时间： $O(K \log K + (K + m) \log m)$ ~O(K \log K + (K + m) \log m)~。其中待判题的稳定排序是 $O(K \log K)$ ~O(K \log K)~（按题号计数排序可降到 $O(K)$ ~O(K)~），有序集合的每次插入与删除是 $O(\log m)$ ~O(\log m)~，而念队名的次数不超过 $K + m + 1$ ~K + m + 1~，故集合操作的总量为 $O((K + m) \log m)$ ~O((K + m) \log m)~。
空间： $O(K + mn)$ ~O(K + mn)~。封榜后的 $K$ ~K~ 条提交都要存下来，每支队伍另需记录每题的失败次数与通过情况。

实现注意事项

罚时以分钟为单位：通过时刻为 $t$ ~t~ 秒时贡献 $\lfloor t / 60 \rfloor$ ~\lfloor t / 60 \rfloor~ 分钟，秒数直接舍去。
封榜的边界是 $4:00:00$ ~4:00:00~，即 $14400$ ~14400~ 秒；这一秒及之前的提交仍然计入排行榜，最后一小时从 $4:00:01$ ~4:00:01~ 开始，只有 $t > 14400$ ~t > 14400~ 的提交才是待判题。
只有通过的题目的失败提交才计罚时，且某题通过之后该队对这一题的提交一律忽略，用位掩码记录已通过的题目可以同时处理这两点。
排名键的三个分量缺一不可，尤其是编号：通过题数与罚时都相同时，先出现在提交记录中的队伍靠前，漏掉它就会在并列数据上出错。
同一道题、同一秒内的多条提交必须按输入顺序揭晓，排序要稳定，用 std::stable_sort 或把提交顺序作为第二关键字参与比较。
一次提交记录都没有的队伍不会出现在排行榜上，也不会被念到队名。
罚时是多题累计的结果，量级可以达到 $10^9$ ~10^9~，用 $64$ ~64~ 位整数保存更稳妥。
评测结果可能含有空格（如 Wrong Answer），读入时应按行读入再手工切分； $K$ ~K~ 最大可达 $2 \times 10^6$ ~2 \times 10^6~，需要关闭流同步 std::ios::sync_with_stdio(false) 或换用更快的读入方式。
输出量同样是 $O(K)$ ~O(K)~ 级别，可以攒进字符串缓冲区一次性输出，避免逐行刷新的开销。
Python 版本与本 C++ 版本算法完全一致，只是常数更大；本题的最大数据建议优先使用 C++。

源代码

#include <algorithm>
#include <iostream>
#include <set>
#include <string>
#include <unordered_map>
#include <vector>

const int MAXN = 20;             // n <= 20，用位掩码记录每题是否通过
const int FREEZE = 240 * 60;     // 封榜时刻 4:00:00 = 14400 秒

struct Submission {
    int prob;                    // 题号，A 记为 0
    int time;                    // 提交时刻（秒）
    bool ac;                     // 是否 Accepted
};

struct Team {
    std::string name;
    int id = 0;                  // 首次出现在提交记录中的编号
    int ac = 0;                  // 已通过题数
    long long penalty = 0;       // 罚时（分钟）
    int solved = 0;              // 位掩码：已通过的题目
    int fails[MAXN] = {};        // 每题通过前的失败提交次数
    std::vector<Submission> pending;   // 封榜后的提交，揭晓前按题号升序排好
    size_t ptr = 0;              // 已经揭晓到第几条待判题
};

// 排名键：通过题数降序、罚时升序、首次出现编号升序。编号唯一，故为全序。
struct Key {
    int ac;
    long long penalty;
    int id;
    int idx;                     // 队伍下标，不参与比较
    bool operator<(const Key &o) const {
        if (ac != o.ac) return ac > o.ac;
        if (penalty != o.penalty) return penalty < o.penalty;
        return id < o.id;
    }
};

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

    int n, m, K;
    std::cin >> n >> m >> K;

    std::vector<Team> teams;
    teams.reserve(m);
    std::unordered_map<std::string, int> index;   // 队名 -> 队伍下标
    index.reserve((size_t)m * 2 + 16);

    std::string line;
    std::getline(std::cin, line);                 // 读掉第一行的行尾
    for (int i = 1; i <= K; i++) {
        std::getline(std::cin, line);

        int t = (line[0] - '0') * 3600 + (line[2] - '0') * 600 + (line[3] - '0') * 60
              + (line[5] - '0') * 10 + (line[6] - '0');
        size_t p = 7;                             // 跳过 "x:yy:zz"
        while (p < line.size() && line[p] == ' ') p++;
        int prob = line[p] - 'A';
        p++;
        while (p < line.size() && line[p] == ' ') p++;
        size_t ns = p;
        while (p < line.size() && line[p] != ' ') p++;
        std::string name = line.substr(ns, p - ns);
        while (p < line.size() && line[p] == ' ') p++;
        bool ac = (line.compare(p, 8, "Accepted") == 0);   // 六种结果中只有它算通过

        auto it = index.find(name);
        int idx;
        if (it == index.end()) {
            idx = (int)teams.size();
            index.emplace(name, idx);
            teams.emplace_back();
            teams[idx].name = std::move(name);
            teams[idx].id = i;
        } else {
            idx = it->second;
        }
        Team &tm = teams[idx];

        if (t <= FREEZE) {
            if (tm.solved >> prob & 1) continue;  // 该题已通过，后续提交无用
            if (ac) {
                tm.penalty += (long long)tm.fails[prob] * 20 + t / 60;
                tm.ac++;
                tm.solved |= 1 << prob;
            } else {
                tm.fails[prob]++;
            }
        } else {
            tm.pending.push_back(Submission{prob, t, ac});
        }
    }

    std::set<Key> board;                          // 有序榜单，begin() 是第一名
    for (size_t i = 0; i < teams.size(); i++) {
        Team &tm = teams[i];
        std::stable_sort(tm.pending.begin(), tm.pending.end(),
                         [](const Submission &a, const Submission &b) { return a.prob < b.prob; });
        board.insert(Key{tm.ac, tm.penalty, tm.id, (int)i});
    }

    std::string out;
    while (!board.empty()) {
        auto it = std::prev(board.end());         // 当前最后一名
        int idx = it->idx;
        Team &tm = teams[idx];
        out += tm.name;
        out += '\n';
        board.erase(it);
        if (board.empty()) break;                 // 念到第一名，滚榜结束
        if (tm.ptr == tm.pending.size()) continue;

        Key worst = *std::prev(board.end());      // 场上新的最后一名
        bool rose = false;
        while (tm.ptr < tm.pending.size()) {
            const Submission &s = tm.pending[tm.ptr++];
            if (tm.solved >> s.prob & 1) continue;      // 该题在封榜前已经通过
            if (s.ac) {
                tm.penalty += (long long)tm.fails[s.prob] * 20 + s.time / 60;
                tm.ac++;
                tm.solved |= 1 << s.prob;
            } else {
                tm.fails[s.prob]++;
            }
            if (Key{tm.ac, tm.penalty, tm.id, idx} < worst) {
                rose = true;                      // 名次上升，立刻转去念新的最后一名
                break;
            }
        }
        if (rose) board.insert(Key{tm.ac, tm.penalty, tm.id, idx});
    }

    std::cout << out;
    return 0;
}

import heapq
import sys


def main():
    data = sys.stdin.buffer.read().split(b"\n")
    n, m, K = map(int, data[0].split())
    FREEZE = 240 * 60                      # 封榜时刻 4:00:00 = 14400 秒

    index = {}                             # 队名 -> 队伍下标
    names = []                             # 队名
    ids = []                               # 首次出现在提交记录中的编号
    acs = []                               # 已通过题数
    pens = []                              # 罚时（分钟）
    solved = []                            # 位掩码：已通过的题目
    fails = []                             # 每题通过前的失败提交次数
    pending = []                           # 封榜后的提交，揭晓前按题号升序排好

    for i in range(1, K + 1):
        line = data[i]
        hh = line[0] - 48
        mm = (line[2] - 48) * 10 + line[3] - 48
        ss = (line[5] - 48) * 10 + line[6] - 48
        t = (hh * 60 + mm) * 60 + ss
        p = 7
        while line[p] == 32:               # 跳过题号前的空格
            p += 1
        prob = line[p] - 65
        p += 2
        start = p
        while line[p] != 32:               # 队名不含空格
            p += 1
        name = line[start:p]
        ac = line[p + 1:p + 9] == b"Accepted"

        idx = index.get(name)
        if idx is None:
            idx = len(names)
            index[name] = idx
            names.append(name)
            ids.append(i)
            acs.append(0)
            pens.append(0)
            solved.append(0)
            fails.append([0] * n)
            pending.append([])

        if t <= FREEZE:
            if solved[idx] >> prob & 1:    # 该题已通过，后续提交无用
                continue
            if ac:
                pens[idx] += fails[idx][prob] * 20 + t // 60
                acs[idx] += 1
                solved[idx] |= 1 << prob
            else:
                fails[idx][prob] += 1
        else:
            pending[idx].append((prob, t, ac))

    # 小根堆，堆顶是当前最后一名：通过题数少的、罚时大的、出现晚的排前面
    heap = []
    for i in range(len(names)):
        pending[i].sort(key=lambda e: e[0])   # 按题号稳定排序，同题内保持提交时间顺序
        heap.append((acs[i], -pens[i], -ids[i], i))
    heapq.heapify(heap)

    ptr = [0] * len(names)
    out = []
    while heap:
        idx = heapq.heappop(heap)[3]
        out.append(names[idx])
        if not heap:
            break                             # 念到第一名，滚榜结束
        if ptr[idx] == len(pending[idx]):
            continue

        worst = heap[0]                       # 场上新的最后一名
        rose = False
        while ptr[idx] < len(pending[idx]):
            prob, t, ac = pending[idx][ptr[idx]]
            ptr[idx] += 1
            if solved[idx] >> prob & 1:       # 该题在封榜前已通过
                continue
            if ac:
                pens[idx] += fails[idx][prob] * 20 + t // 60
                acs[idx] += 1
                solved[idx] |= 1 << prob
            else:
                fails[idx][prob] += 1
            if (acs[idx], -pens[idx], -ids[idx], idx) > worst:
                rose = True
                break
        if rose:
            heapq.heappush(heap, (acs[idx], -pens[idx], -ids[idx], idx))

    sys.stdout.buffer.write(b"".join(name + b"\n" for name in out))


main()

目前没有评论。