#CCSP2024E. 追踪检测

追踪检测

本题的部分题意表述不清，我们根据 std 进行了补全，并标注补全位置。

时间限制： 1.0 秒

空间限制： 512 MB

题目背景

小 K 是一位热爱古典游戏的年轻人。这些游戏承载了他童年的美好回忆，但随着时间的推移，许多经典游戏已经在网络上难以找到。小 K 不甘心让这些珍贵的记忆消失，于是他决定采取行动。

小 K 发现，通过 BT 协议可以方便地共享文件，于是他萌生了一个想法：组织一个内部的游戏分享社区，让志同道合的朋友们一起来分享和下载这些古典游戏。很快，他在网上找到了几个同样热爱古典游戏的伙伴，大家决定一起行动。

然而，小 K 意识到，虽然 BT 协议非常方便，但也存在一些法律和合规问题。如果不加以控制，可能会出现版权侵权等问题。为了保证大家在用 BT 协议时是合法合规的，他决定写一个 tracker 服务器，在实现基本的 BT 协议功能的同时，加入一些额外的检查机制，以确保共享的游戏都是合法的。

BT 下载（BitTorrent 下载）是一种点对点（P2P）文件共享协议，通过将大文件分割成小块并在多个用户之间传输，实现高效的文件分发。

每个参与下载的用户不仅仅是下载者，同时也充当上传者，分享已经下载到的文件块，极大地提高了下载速度和效率。

Tracker服务器在BT下载中扮演关键角色。 它负责管理和协调所有参与下载的用户，记录每个用户的IP地址和所拥有的文件块信息。

当用户请求下载文件时，Tracker 服务器会提供其他拥有该文件块的用户列表，使得下载者能够从多个源头获取数据。

Tracker 服务器本身并不存储文件，只提供元数据和连接信息，确保 BT 网络的正常运作。

在本题中，你需要帮助小 K 实现一个满足要求的 BitTorrent Tracker。

题目描述

小 K 要实现的 Tracker 服务器从标准输入中读取请求。

每个请求都会以 1 个回车为结尾（\n，ASCII 码为 0x0a）。

对于每个请求，服务端都应当向标准输出写入响应。

每个响应都需要以 1 个回车为结尾（\n，ASCII 码为 0x0a）。

小 K 的 Tracker 需要实现对以下请求的响应：

announce 请求

一个 announce 请求包含以下参数：

  • info_hash，请求的资源的标识符，由 20 个可打印的 ASCII 字符组成。
  • peer_id，20 个字符（均为可打印的 ASCII 字符）的唯一客户端标识符，每个客户端的 peer_id 不相同。
  • IP，客户端的 IP 地址，均为 IPv4 地址。（补充说明：每个客户端对应唯一的 IP 地址。）
  • port，客户端正在监听的端口（十进制数字表示）。
  • uploaded，当前已经上传的文件的字节数 (十进制数字表示)。
  • downloaded，当前已经下载的文件的字节数 (十进制数字表示)。
  • numwant，可选，希望 Tracker 返回的 peer 数目，若不填，默认返回 50 个 IP 和 Port。
  • event，可选，该参数的值可以是 started，completed，stopped，empty 其中的一个，该参数的值为 empty 与该参数不存在是等价的，当开始下载时，该参数的值设置为 started，当下载完成时，该参数的值设置为 completed，当停止下载/上传时，该参数的值设置为 stopped。

如何响应 announce 请求

当收到一个 announce 请求时，Tracker 需要先查询客户端所请求的 info_hash 是否有效，若无效，则报错 invalid info_hash。

随后根据 event 执行不同的操作：

  • 若 event=started，则将用户变为该种子的 leecher，如果用户已经为 leecher，则无需更改此状态。
  • 若 event=completed，则将该用户变为该种子的 seeder，如果用户已经为 seeder，则无需更改此状态。
  • 若 event=stopped，则将该用户从 leechers/seeders 中删除，若用户原本就不是该种子的 seeder/leecher，则无需操作。
  • 若 event=empty，则不需要改变用户的 leecher/seeder 状态，若用户原本就不是该种子的 seeder/leecher，则无需操作。

在上述操作完成之后，如果用户依然存在，则更新用户对该种子的 uploaded，downloaded。注意，在 announce 中的 uploaded 和 downloaded 的具体数值并非递增，后续 announce 中的 uploaded 和 downloaded 数值可能会减少，请不要对其有单调递增的假设。

最后，根据用户状态返回 peers 列表（可能包括用户自己）：

  • 用户为 leecher：返回 numwant 个 seeders（若 seeders 不够，则用 leechers 补足，如果还不够，则返回所有 seeders 和 leechers）。
  • 用户为 seeder：返回 numwant 个 leechers（若 leechers 不够，则返回所有 leechers）。
  • 用户不存在或者被删除：返回空的 peers 列表。

请求失败时，Tracker 返回 ERROR 和错误原因。 请求成功时，Tracker 返回 OK 和以下内容：

  • peers，是一个列表，每一个元素都包含有三个内容，分别为：
    • peer_id，peer 节点的 Id。
    • IP，peer 节点的 IP 地址。
    • Port，peer 节点的端口。

为了保证结果的唯一性，若返回的 peers 不为空，则需要按照以下规则排序：

  1. 若返回的 peers 全为 seeders，则需要按照其 uploaded 降序排列，当出现两个 seeders 的 uploaded 相等时，按照 peer id 字典序排列，字典序小的排在前面。
  2. 若返回的 peers 全为 leechers，则需要按照其 downloaded 降序排列，当出现两个 leechers 的 downloaded 相等时，按照 peer id 字典序排列，字典序小的排在前面。
  3. 若返回的 peers 同时包含 seeders 和 leechers，需要将所有的 seeders 排在 leechers 之前，seeders 之间按照上述第一条规则排序，leechers 之间按照上述第二条规则排序。

特殊情况：对于处于异常状态（比如被封禁和被冻结）的种子，只处理 event=stopped 请求。

scrape 请求

无参数。

如何响应 scrape 请求

返回 OK 和 Tracker 记录的所有种子的情况，包括每个种子的 info_hash，种子是否被封禁，是否被冻结，和该种子的做种人数（num_seeders）和正在下载的人数（num_leechers）。

结果按照种子的 info_hash 字典序排列。

add 请求

新增一个种子。

包含一个 info_hash 参数，格式与 announce 请求中的 info_hash 相同。

如何响应 add 请求

如果种子已经存在，则无法重复添加，返回 ERROR；若添加成功，则返回 OK。

del 请求

删除一个种子。

注意，当一个种子正在被一些 peer 使用时，无法直接删除该种子。 此时，该种子进入到冻结状态，新加入的 peer 无法通过 announce 获取到该种子的信息， 等所有现存使用该种子的 peer 离线（或者 stopped）之后，该种子被真正删除。

包含一个 info_hash 参数，格式与 announce 请求中的 info_hash 相同。

补充说明：种子的是否被冻结、是否被封禁是两种独立的状态。

如何响应 del 请求

如果种子不存在，则无法删除，返回 ERROR；若直接成功，则返回 OK；若种子进入冻结状态（包括该请求之前已经为冻结状态），则返回 FROZEN。

run 请求

模拟时间流逝，包含一个 time 参数（十进制数字），表示过去了多少秒。

考虑到客户端可能未发出任何停止请求就直接离线，Tracker 会通过超时机制清理客户端，即若客户端对某个种子长期不发出 announce 请求，Tracker 需要将其从种子的 peers（seeders或leechers）列表中删除。

如何响应 run 请求

更新每个种子的 peers 列表，超时的 peers 需要从 peers 列表中删除。

Tracker 需要记录每个 peer 最近一次 announce 的时间，如果当前时间与最近一次 announce 时间超过了 60 秒，则需要将该 peer 删除。

注意，一个客户端对种子X发出的 announce 请求并不会刷新其对种子Y的 announce 时间。

返回 OK。

补充说明：每一条指令本身不会带来时间流逝。设初始的时间为 0，则只有 run 指令会使得时间往前走。每次 announce 指令的时间即为当前的时间。

report 请求

report 请求会导致以下变化：

  1. 该种子处于被封禁状态
  2. 所有正在上传或者下载该种子的客户端变为被封禁状态。服务器仅处理被封禁客户端的 event=stopped 的 announce 请求。一个客户端在停止了其所有被封禁的种子的上传和下载后，其封禁状态才会被解除。
  3. 被封禁的客户端不会被作为 seeder 或者 leecher 发送给其他客户端。

如果种子不存在，则无法举报，返回 ERROR；若举报成功，则返回 OK。

输入格式

从标准输入读入数据。

输入由若干行组成，每行由空格分隔为若干段，第一段包含一个请求命令，表示需要进行的操作，之后的若干段表示的是操作的参数，参数名均为大写。

  • announce 操作：announce INFO_HASH=0...0 PEER_ID=X...X IP=111.111.111.111 PORT=2222 UPLOADED=0 DOWNLOADED=0 NUMWANT=50 EVENT=started
  • scrape 操作：scrape
  • add 操作：add INFO_HASH=00000000000000000000，表示向 Tracker 中添加 info_hash 为 00000000000000000000 的种子
  • del 操作：del INFO_HASH=00000000000000000000，表示删除 Tracker 中 info_hash 为 00000000000000000000 的种子记录
  • run 操作：run 5，表示时间经过 5 秒
  • report 操作：report INFO_HASH=00000000000000000000，表示举报 info_hash 为 00000000000000000000 的种子

输出格式

输出到标准输出。

你的输出应由若干行组成，每一行对应一个输入操作的响应。 每一行由空格分隔的结果和一个可选的字符串组成，分别表示响应结果（OK/ERROR）和可能存在的返回值，具体的返回值格式如下：

  • announce 操作：
    • 若 info_hash 无效，返回如下结果：ERROR: Invalid info_hash
    • 若 info_hash 被封禁，返回：ERROR: Torrent banned
    • 若 info_hash 被冻结，返回：ERROR: Torrent frozen
    • 若客户端被封禁，返回：ERROR: Client banned
    • 若 peers 为空，返回如下结果：OK: COMPLETE=2 INCOMPLETE=1 PEERS=[]
    • 若 peers 不为空，返回如下格式结果：OK: COMPLETE=2 INCOMPLETE=1 PEERS=[(X...X,111.111.111.111,2222),(Y...Y,222.222.222.222,6666)]
  • scrape 操作：
    • 若 Tracker 中无任何记录的种子，返回如下结果：OK: []
    • 按照 info_hash 字典序返回 Tracker 记录的所有种子，类似如下结果：OK: [(0...0,B=0,F=0,1,1), (1...1,B=0,F=0,2,1)]，其中 B= 和 F= 分别表示封禁和冻结状态，1 表示有该状态， 0 表示无该状态。
  • add 操作：返回OK或者ERROR: Torrent already exists
  • del 操作：返回OK或者ERROR: Invalid info_hash或者FROZEN
  • run 操作：返回如下结果：OK
  • report 操作：返回 OK 或者 ERROR: Invalid info_hash
add INFO_HASH=INFO-000000000000001
add INFO_HASH=INFO-000000000000002
add INFO_HASH=INFO-000000000000003
announce INFO_HASH=INFO-000000000000001 PEER_ID=PEER-00000000000000A IP=192.168.3.1 PORT=5204 UPLOADED=10 DOWNLOADED=20 NUMWANT=3 EVENT=completed
announce INFO_HASH=INFO-000000000000001 PEER_ID=PEER-00000000000000B IP=192.168.3.2 PORT=5204 UPLOADED=0 DOWNLOADED=0 NUMWANT=3 EVENT=started
announce INFO_HASH=INFO-000000000000003 PEER_ID=PEER-00000000000000C IP=192.168.3.3 PORT=5204 UPLOADED=3500 DOWNLOADED=500 NUMWANT=3 EVENT=started
announce INFO_HASH=INFO-000000000000002 PEER_ID=PEER-00000000000000D IP=192.168.3.4 PORT=5204 UPLOADED=1200 DOWNLOADED=300 NUMWANT=3 EVENT=completed
scrape
del INFO_HASH=INFO-000000000000003
scrape
run 20
announce INFO_HASH=INFO-000000000000003 PEER_ID=PEER-00000000000000B IP=192.168.3.2 PORT=5204 UPLOADED=120 DOWNLOADED=1000 NUMWANT=3 EVENT=started
announce INFO_HASH=INFO-000000000000001 PEER_ID=PEER-00000000000000C IP=192.168.3.3 PORT=5204 UPLOADED=1000 DOWNLOADED=200 NUMWANT=3 EVENT=empty
announce INFO_HASH=INFO-000000000000001 PEER_ID=PEER-00000000000000A IP=192.168.3.1 PORT=5204 UPLOADED=1000 DOWNLOADED=300 NUMWANT=3 EVENT=empty
run 20
announce INFO_HASH=INFO-000000000000001 PEER_ID=PEER-00000000000000B IP=192.168.3.2 PORT=5204 UPLOADED=120 DOWNLOADED=1000 NUMWANT=3 EVENT=empty
announce INFO_HASH=INFO-000000000000001 PEER_ID=PEER-00000000000000C IP=192.168.3.3 PORT=5204 UPLOADED=3500 DOWNLOADED=500 NUMWANT=3 EVENT=started
announce INFO_HASH=INFO-000000000000001 PEER_ID=PEER-00000000000000D IP=192.168.3.4 PORT=5204 UPLOADED=1200 DOWNLOADED=300 NUMWANT=3 EVENT=completed
announce INFO_HASH=INFO-000000000000001 PEER_ID=PEER-00000000000000E IP=192.168.3.5 PORT=5204 UPLOADED=1200 DOWNLOADED=300 NUMWANT=3 EVENT=started
announce INFO_HASH=INFO-000000000000002 PEER_ID=PEER-00000000000000B IP=192.168.3.2 PORT=5204 UPLOADED=120 DOWNLOADED=1000 NUMWANT=3 EVENT=started
report INFO_HASH=INFO-000000000000002
scrape
announce INFO_HASH=INFO-000000000000001 PEER_ID=PEER-00000000000000C IP=192.168.3.3 PORT=5204 UPLOADED=3500 DOWNLOADED=500 NUMWANT=3 EVENT=empty
announce INFO_HASH=INFO-000000000000002 PEER_ID=PEER-00000000000000D IP=192.168.3.4 PORT=5204 UPLOADED=1200 DOWNLOADED=300 NUMWANT=3 EVENT=stopped
announce INFO_HASH=INFO-000000000000001 PEER_ID=PEER-00000000000000C IP=192.168.3.3 PORT=5204 UPLOADED=3500 DOWNLOADED=500 NUMWANT=3 EVENT=empty
scrape
run 50
scrape

OK
OK
OK
OK: COMPLETE=1 INCOMPLETE=0 PEERS=[]
OK: COMPLETE=1 INCOMPLETE=1 PEERS=[(PEER-00000000000000A,192.168.3.1,5204),(PEER-00000000000000B,192.168.3.2,5204)]
OK: COMPLETE=0 INCOMPLETE=1 PEERS=[(PEER-00000000000000C,192.168.3.3,5204)]
OK: COMPLETE=1 INCOMPLETE=0 PEERS=[]
OK: [(INFO-000000000000001,B=0,F=0,1,1),(INFO-000000000000002,B=0,F=0,1,0),(INFO-000000000000003,B=0,F=0,0,1)]
FROZEN
OK: [(INFO-000000000000001,B=0,F=0,1,1),(INFO-000000000000002,B=0,F=0,1,0),(INFO-000000000000003,B=0,F=1,0,1)]
OK
ERROR: Torrent frozen
OK: COMPLETE=1 INCOMPLETE=1 PEERS=[]
OK: COMPLETE=1 INCOMPLETE=1 PEERS=[(PEER-00000000000000B,192.168.3.2,5204)]
OK
OK: COMPLETE=1 INCOMPLETE=1 PEERS=[(PEER-00000000000000A,192.168.3.1,5204),(PEER-00000000000000B,192.168.3.2,5204)]
OK: COMPLETE=1 INCOMPLETE=2 PEERS=[(PEER-00000000000000A,192.168.3.1,5204),(PEER-00000000000000B,192.168.3.2,5204),(PEER-00000000000000C,192.168.3.3,5204)]
OK: COMPLETE=2 INCOMPLETE=2 PEERS=[(PEER-00000000000000B,192.168.3.2,5204),(PEER-00000000000000C,192.168.3.3,5204)]
OK: COMPLETE=2 INCOMPLETE=3 PEERS=[(PEER-00000000000000D,192.168.3.4,5204),(PEER-00000000000000A,192.168.3.1,5204),(PEER-00000000000000B,192.168.3.2,5204)]
OK: COMPLETE=1 INCOMPLETE=1 PEERS=[(PEER-00000000000000D,192.168.3.4,5204),(PEER-00000000000000B,192.168.3.2,5204)]
OK
OK: [(INFO-000000000000001,B=0,F=0,2,3),(INFO-000000000000002,B=1,F=0,1,1),(INFO-000000000000003,B=0,F=1,0,1)]
OK: COMPLETE=2 INCOMPLETE=3 PEERS=[(PEER-00000000000000A,192.168.3.1,5204),(PEER-00000000000000C,192.168.3.3,5204),(PEER-00000000000000E,192.168.3.5,5204)]
OK: COMPLETE=0 INCOMPLETE=1 PEERS=[]
OK: COMPLETE=2 INCOMPLETE=3 PEERS=[(PEER-00000000000000D,192.168.3.4,5204),(PEER-00000000000000A,192.168.3.1,5204),(PEER-00000000000000C,192.168.3.3,5204)]
OK: [(INFO-000000000000001,B=0,F=0,2,3),(INFO-000000000000002,B=1,F=0,0,1),(INFO-000000000000003,B=0,F=1,0,1)]
OK
OK: [(INFO-000000000000001,B=0,F=0,1,3),(INFO-000000000000002,B=1,F=0,0,1)]

样例 1 解释

下面对应每一行的输出说明：

  1. 添加成功
  2. 添加成功
  3. 添加成功
  4. A 开始做种资源 1，没有下载者，所以 peers 为空
  5. B 开始下载资源 1，peers 里面为 A 和自己
  6. C 开始下载资源 3，peers 里面只有自己
  7. D 开始做种资源 2，没有下载者，peers 为空
  8. scrape 看到三个种子
  9. 删除资源 3，有人正在下载，所以冻结
  10. scrape 看到冻结状态
  11. 时间流逝 20 秒
  12. B 开始下载资源 3，因为资源被冻结，所以返回错误
  13. C 报告其资源 1 的进度，但是 C 从未宣称上传/下载资源 1，因此返回基本信息，但是 peers 返回空
  14. A 报告其资源 1 的进度，A 在做种，所以 peers 中看到下载者 B
  15. 时间流逝 20 秒
  16. B 报告其资源 1 的进度，B 在下载，所以 peers 中看到 A 和自己
  17. C 开始下载资源 1，看到做种的 A 和正在下载的 B
  18. D 开始做种资源 1，看到正在下载的 B 和 C，B 下载的更多，所以排在前面
  19. E 开始下载资源 1，看到正在做种的 D 和 A（D 上传量更多），然后看到下载的 B（B 比 C 下载量更大）
  20. B 开始下载资源 2，看到正在上传的 D 和正在下载的自己
  21. 举报资源 2，返回成功
  22. scrape 看到封禁状态
  23. C 报告其资源 1 的进度，C 的状态是正在下载，peers 中看到了正在做种的 A（看不到 D 因为被封禁了）、自己、和正在下载的 E（看不到 B 因为被封禁了）
  24. D 停止了资源 2 的做种
  25. C 报告其资源 1 的进度，C 的状态是正在下载，peers 中看到了正在做种的 D（已经被解除封禁）、正在做种的 A，和自己
  26. scrape 查看当前状态
  27. 时间流逝 50 秒
  28. scrape 查看当前状态，因为时间流逝，下载资源 3 的 C 信息失效，C 是最后一个访问资源 3 的客户端，因此资源 3 得以删除，同时 A 做种资源 1 的信息也过期失效，因而资源 1 的做种数也减少了 1

子任务

测试点 行数 包含的命令
1 100100 announce, add, del
2 10001000
3 10410^4
4 10001000 announce, add, del, scrape
5 10410^4
6 announce, add, del, scrape, run
7 5×1045\times 10^4
8 10510^5 announce, add, del, scrape, run, report
9
10
  1. About
  2. Contact Us
  3. Privacy
  4. Terms of Service
  5. Copyright Complaint
  6. Language
  7. Legacy mode
  8. Theme
  2. 湘ICP备2024052008号 | Copyright © 2025 - 至今 水木清研. All rights reserved.
  3. Worker 0, 45ms
  4. Powered by Hydro v5.0.0-beta.2 Community