UOJ Logo Universal Online Judge

UOJ

#964. 【APIO2025】Hack!

附件下载 统计

你参加了一场 Codeforces 的编程比赛,现在离比赛结束只有一个小时了。你发现同房间的另外一位选手通过使用 unordered_set 通过了一道题目。是时候把他的代码 hack 掉了!

你知道 unordered_set 是使用一个包含 n 个桶的哈希表实现的,其中桶的编号为 0n1。不过很可惜,你并不知道 n 具体是多少,所以你希望通过下面的操作将 n 还原出来。

当你将一个整数 x 插入哈希表时,它将会被插入到第 (xmodn) 个桶中。如果在这次插入之前这个桶中已经有 b 个元素,这将会导致 b 次哈希冲突的产生。

每次操作中,你可以向交互库提交 k 个不同的整数 x[0],x[1],,x[k1] 进行查询,交互库会依次将这些整数插入到哈希表中,并返回创建包含这些数字的哈希表会引起的哈希冲突总次数。然而,向交互库提交一次包含 k 个不同的整数的查询需要 k 的花费。

例如,当 n=5 时,如果你向交互库提交数组 x=[2,15,7,27,8,30],将会引起总共 4 次哈希冲突,具体如下:

操作 新增哈希冲突次数 桶状态
初始状态 - [], [], [], [], []
插入 x[0]=2 0 [], [], [2], [], []
插入 x[1]=15 0 [15], [], [2], [], []
插入 x[2]=7 1 [15], [], [2, 7], [], []
插入 x[3]=27 2 [15], [], [2, 7, 27], [], []
插入 x[4]=8 0 [15], [], [2, 7, 27], [8], []
插入 x[5]=30 1 [15, 30], [], [2, 7, 27], [8], []

请注意:交互库在每次你提交的时候都将 unordered_set 初始化为空集,然后把提交的数字依次插入来创建哈希表。也就是说,每一次的交互查询是相互独立的。

你的任务是使用不超过 1000000 的花费求出桶的数量 n

实现细节

你需要实现以下函数:

int hack()
  • 该函数返回一个整数 n
  • 对于每个测试点,评测程序可能会调用该函数多于一次。每次调用都应该当做新的情况分别处理。

在这个函数中,你可能会调用以下交互函数:

long long collisions(std::vector<long long> x)
  • x:一个包含不同整数的数组,其中对于所有 i,满足 1x[i]1018
  • 该函数返回一个整数,表示将数组 x 中所有元素依次插入哈希表引起的哈希冲突次数。
  • 该函数可以多次调用。在一次 hack() 的调用中,多次调用的数组 x 的总长度不能超过 1000000

注意:由于 hack() 函数调用可能会发生多次,选手需要注意之前调用的残余数据对于后续调用的影响,尤其是全局变量的状态。

1000000 的花费限制应用于每一组测试数据。即,如果 hack() 函数被调用了 t 次,你可以使用不超过 t×1000000 的总花费,并且每次独立调用 hack() 时的花费不能超过 1000000

n 的值在交互函数调用前已经固定。

例子

假设有两组测试用例,评测程序将首先调用 hack() 函数:

hack()

在这个函数中,你可以进行以下调用:

函数调用 返回值
collisions([2, 15, 7, 27, 8, 30]) 4
collisions([1, 2, 3]) 0
collisions([10, 20, 30, 40, 50]) 10

如果你还原出 n=5,那么函数 hack() 返回 5。

接下来,评测程序将再一次调用 hack() 函数:

hack()

在这个函数中,你可以进行以下调用:

函数调用 返回值
collisions([1, 3]) 1
collisions([2, 4]) 1

你从上述调用中还原出唯一满足的 n 是 2,那么函数 hack() 返回 2。

约束条件

  • 1t10,其中 t 为每组测试点中的测试用例数量。
  • 2n109
  • 对于每次 collisions() 调用,1x[i]1018

子任务

  1. (8 分) n500000
  2. (17 分) n1000000
  3. (75 分) 没有额外的约束条件。

在最后一个子任务中,你可以获得部分分。令 q 为该子任务下所有测试用例 hack() 函数中的最大总花费。该子任务的部分分计算如下:

条件 分数
1000000<q 0
110000<q1000000 75log50(106x90000)
q110000 75

在任意测试用例中,如果对 collisions() 函数调用不满足实现细节中的约束条件,或者 hack() 函数调用的返回值错误,该子任务的分数为 0。

评测程序示例

评测程序示例按以下格式读取输入:

  • 第 1 行:t

对于接下来 t 组数据的每一组:

  • 第 1 行:n

对于每组测试用例,令 m 为函数 hack() 的返回值,c 为所有查询的总花费。评测程序示例按以下格式打印你的答案:

  • 第 1 行:mc