题目来自 CCSP2025 T2，评测使用官方数据和自造高质量复刻数据。我们承认原始题面、大样例、官方数据版权均归中国计算机学会（CCF）所有，因此题面与评测服务均免费对外开放。如果您认为我们侵犯了您的权益，可联系我们。

原题数据范围表述不清，因此我们基于官方数据对描述进行补全，并基于不同做法的区分度增加一组民间评测的子任务，原子任务 4 调整为 20 分，新增 30 分的子任务 5。

时间限制： 1.0 秒

空间限制： 512 MiB

题目背景

现代应用编程语言通常使用垃圾回收 (Garbage Collection, GC) 支持堆内存回收，回收的堆内存可用于后续的内存分配。堆内存的使用就是一个内存“分配-回收-分配”的循环。支持内存自动分配和回收的堆称为“受管堆 (Managed Heap)”。受管堆内存回收过程中，活对象标记是不可或缺的环节，各类 GC 都是基于活对象标记算法识别堆中的存活对象，据此对堆内存进行相应处理完成内存回收重用。活对象标记过程是从给定的根指针集合出发，递归遍历根指针直接或者间接指向的所有对象，被遍历到的对象就是活对象，反之就是死对象，死对象占据的内存可被回收用于后续内存分配。

题目描述

在本题中，受管堆是如下定义的一个数据结构：

1. 包含一段地址连续的内存。
2. 内存中储存有一至多个对象，分布在内存空间中，对象占用的内存彼此不重叠。
3. 对象中依次存放着 $1$ 个类型 ID，若干（大于或等于 $0$）个引用字段，其值是某个对象的地址；其余字段为值。类型 ID 用于指明该对象的大小，以及该对象的引用成员所在的偏移位置。
4. 根指针集合中的元素是指向堆中对象的指针。

以根指针集合中的元素作为遍历起点，堆中所有可遍历对象构成了一个带有根节点的有向图，活对象是其中的节点，活对象的引用成员是指向其它活对象的边。遍历该有向图的过程称为“标记 (Mark)”，可识别出堆中所有的活对象。

堆文件及其格式

本题设定受管堆内存具有下图所示的结构：

对象格式

堆数据文件是堆内存的转储文件，以二进制数据形式提供，它包含了对象的二进制数据。对象在内存中的数据结构定义如下（假设指针为 $64$ 位宽度，对象成员地址按照 $8$ 字节对齐）：

struct Object {
    TypeId tid; // 类型的 ID
    uint64_t val[]; // 引用成员和值成员构成的数组
};

对象包含类型信息、值字段和引用字段。如下为一个对象的示例：{5, 200, 400, 0x1230, 0x5678, 100, 300}。其中的 $5$ 表示类型的 ID。后续数据的解释需要参照具体的类型信息。假如 ID 为 $5$ 的类型为 {56, 24, 32}，即该类型对象的大小为 $56$，包含两个引用字段，偏移量分别为 $24$ 和 $32$ 字节，对应第 $3$ 和 $4$ 个成员，即 0x1230、0x5678。其余成员（$200$、$400$、$100$、$300$）均为值类型，不会引用其他对象。注意，这里的大小是包含对象头部的“类型 ID”的，引用字段的偏移量同样是包含头部的“类型 ID”，因而引用字段的偏移量一定不为 $0$。

你需要完成以下两个任务：

任务一：标记活对象

分析给定的堆镜像文件，根据堆信息中指定的根指针遍历堆中活对象，统计活对象的数量和所占内存大小。

任务二：完成内存分配

在上述给定的堆中完成一组新的对象内存分配请求。

活对象正在占据的内存不可用于分配，其余所有内存均为“空闲内存”，可用于分配新对象。分配内存是从空闲内存中找到一份连续的内存空间且其大小不小于给定的正整数。

• 如果连续的“空闲内存”足够大可直接用于分配指定大小，则分配开销计为 $0$。
• 如果“空闲内存”不够大，则需要先选择并迁移一些活对象到外部内存，形成更大的连续空闲内存块，再进行分配。为简化问题，假定外部内存不在堆中，且空间无限大。

迁移对象的开销包括两个部分：

1. 对象本身的大小（以字节为单位）；
2. 对象迁移到外部内存后，需要更新所有指向该对象的指针，包括根指针和活对象（也包括外部内存上的对象）中存储的旧指针，其开销为需要修改的指针个数 $\times 8$。

这组分配请求由 $N$ 个整数 $R_i$ 组成，依次表示对象所需的内存大小。这组对象的分配需要满足以下两条要求：

• 第 $i$ 个对象分配到的地址 $A_i$，要小于第 $i+1$ 个对象分配得到的地址 $A_{i+1}$，即对于 $i<j$，需要满足 $A_i<A_j$。
• 这一组新的对象必须位于堆内存，不能被迁移到外部内存。

你需要计算出满足这组对象分配所需要的最小开销。

输入格式

从标准输入读入数据。

标准输入的第一行包含五个整数：堆的起始地址 $A$（十六进制），堆的大小 $S$、对象类型数 $T$、根指针数量 $P$、新的对象分配请求数量 $N$。

之后 $T$ 行，依次给出 ID 为 $1$ 到 $T$ 的类型描述。对象类型描述为一组空格隔开的整数，第一个整数为该类型对象占内存的大小，之后的若干个整数表示该对象中各个引用成员的偏移量。

之后 $P$ 行，每行表示一个根指针（十六进制）。

之后 $N$ 行，每行一个整数 $R_i$ 表示需要分配的对象的大小。注意，所有分配的对象地址需要 $64$ 位对齐。

再之后的若干行，每行一对十六进制数字（空格隔开），分别表示一个 $8$ 对齐的内存地址和该内存地址上的 $64$ 位数据，这部分数据不需要模拟字节序，直接按给出的数据读取即可。

输出格式

输出到标准输出。

输出两行。第一行为两个整数，分别代表活对象的数量和所占内存的大小。第二行为一个整数，表示完成所有新对象分配所需的最小开销。如果无法完成分配，输出 $-1$。

0x10474da80 1024 4 2 5
24
16
56 8
16
0x10474dc08
0x10474dc90
48
56
32
56
32
0x10474da80 0x0
0x10474da88 0x0
0x10474da90 0x0
0x10474da98 0x0
0x10474daa0 0x0
0x10474daa8 0x2
0x10474dab0 0x693483a802f41f53
0x10474dab8 0x0
0x10474dac0 0x0
0x10474dac8 0x0
0x10474dad0 0x0
0x10474dad8 0x0
0x10474dae0 0x0
0x10474dae8 0x0
0x10474daf0 0x0
0x10474daf8 0x0
0x10474db00 0x0
0x10474db08 0x0
0x10474db10 0x0
0x10474db18 0x0
0x10474db20 0x0
0x10474db28 0x0
0x10474db30 0x0
0x10474db38 0x0
0x10474db40 0x0
0x10474db48 0x0
0x10474db50 0x0
0x10474db58 0x0
0x10474db60 0x0
0x10474db68 0x0
0x10474db70 0x3
0x10474db78 0x10474dc28
0x10474db80 0xed2137a628ed34b
0x10474db88 0x761d0a5401fcb630
0x10474db90 0x376f114f6c914d60
0x10474db98 0x48cfdac05cd975f7
0x10474dba0 0x950472146229898
0x10474dba8 0x0
0x10474dbb0 0x0
0x10474dbb8 0x1
0x10474dbc0 0x147709ab7b800f75
0x10474dbc8 0x3e3f9a1131bc40c
0x10474dbd0 0x0
0x10474dbd8 0x0
0x10474dbe0 0x0
0x10474dbe8 0x0
0x10474dbf0 0x0
0x10474dbf8 0x0
0x10474dc00 0x0
0x10474dc08 0x1
0x10474dc10 0xd457cb56c19bb05
0x10474dc18 0x4db84e444cfe55e1
0x10474dc20 0x0
0x10474dc28 0x2
0x10474dc30 0x234e33b97f1a7a38
0x10474dc38 0x0
0x10474dc40 0x0
0x10474dc48 0x0
0x10474dc50 0x0
0x10474dc58 0x0
0x10474dc60 0x0
0x10474dc68 0x0
0x10474dc70 0x0
0x10474dc78 0x1
0x10474dc80 0x45a178a06325c8ca
0x10474dc88 0x13f87ba6bf67416
0x10474dc90 0x2
0x10474dc98 0x2734f1db71e7c4f9
0x10474dca0 0x0
0x10474dca8 0x0
0x10474dcb0 0x0
0x10474dcb8 0x0
0x10474dcc0 0x0
0x10474dcc8 0x1
0x10474dcd0 0x49dd89f804f274f9
0x10474dcd8 0x19d8641d6f8d1eaa
0x10474dce0 0x0
0x10474dce8 0x0
0x10474dcf0 0x0
0x10474dcf8 0x0
0x10474dd00 0x2
0x10474dd08 0x5f091f7e4d94b92c
0x10474dd10 0x2
0x10474dd18 0x488d64914ff2b9f0
0x10474dd20 0x0
0x10474dd28 0x0
0x10474dd30 0x0
0x10474dd38 0x0
0x10474dd40 0x0
0x10474dd48 0x0
0x10474dd50 0x0
0x10474dd58 0x0
0x10474dd60 0x0
0x10474dd68 0x0
0x10474dd70 0x0
0x10474dd78 0x1
0x10474dd80 0xa5a0e03ac590cd
0x10474dd88 0x1db4fc3179e4d274
0x10474dd90 0x0
0x10474dd98 0x0
0x10474dda0 0x0
0x10474dda8 0x0
0x10474ddb0 0x0
0x10474ddb8 0x0
0x10474ddc0 0x0
0x10474ddc8 0x0
0x10474ddd0 0x0
0x10474ddd8 0x0
0x10474dde0 0x0
0x10474dde8 0x1
0x10474ddf0 0x5d62dbea55190433
0x10474ddf8 0x51c8b30f05540f8c
0x10474de00 0x0
0x10474de08 0x0
0x10474de10 0x0
0x10474de18 0x0
0x10474de20 0x0
0x10474de28 0x0
0x10474de30 0x3
0x10474de38 0x10474dd00
0x10474de40 0x786fb32b08f2bd63
0x10474de48 0x3588f2156d5c09d2
0x10474de50 0x215d5fa331cd5c28
0x10474de58 0x373779e07931d771
0x10474de60 0x7559d5481b227d72
0x10474de68 0x0
0x10474de70 0x0
0x10474de78 0x0

2 40
0

子任务

记活对象总数量为 $K$，对象大小为 $L$。所有数据满足：

• $0\le K\le 500$；
• $0\le A\le 10^{12}$，$A$ 为 $8$ 的倍数；
• $8\le S\le 10^7$，$S$ 为 $8$ 的倍数；
• $1\le T\le 1000$，$0\le P\le 1000$；
• 允许没有被使用的类型，也允许多个根指向同一个对象；
• $8\le L\le S$，$L$ 为 $8$ 的倍数；同一类型的引用偏移互不相同，均为 $8$ 的倍数，且位于 $[8,L-8]$。所有类型的引用偏移总数不超过 $10^5$；
• $1\le N\le 500$，每次请求大小为不超过 $10^7$ 的正 $8$ 倍数；请求大小之和可以超过堆大小，此时输出第二行为 $-1$；
• 内存镜像最多包含 $2\times 10^5$ 行，地址互不相同，均为 $8$ 的倍数且属于 $[A,A+S)$；每个十六进制数使用 0x 前缀，后接 $1$ 至 $16$ 个十六进制数字；
• 内存镜像没有列出的字，其值视为 $0$；堆中至少存在一个对象；对象之间不重叠；根和对象的引用字段均指向实际对象的起始地址；非引用字段可以保存任意无符号 $64$ 位整数；
• 同一个对象只计一次活对象，但每个根和每个活对象的引用字段分别计入迁移开销；死对象的引用不计入。即使引用的来源对象也迁出，原有引用字段仍计入目标对象的迁移开销；
• 输入文件大小不超过 1 MB。

本题采用捆绑测试，你只有通过一个子任务中的所有测试点才能得到该子任务的分数。

子任务编号	分值	$K\le$	$S\le$	$N\le$
1	10	$10$	$10^6$	$5$
2	30	$30$
3	10	$40$	$10^7$	$200$
4	20	$200$
5	30	$500$		$500$