你参加了一场 Codeforces 的编程比赛,现在离比赛结束只有一个小时了。你发现同房间的另外一位选手通过使用 unordered_set
通过了一道题目。是时候把他的代码 hack 掉了!
你知道 unordered_set
是使用一个包含
当你将一个整数
每次操作中,你可以向交互库提交
例如,当
操作 | 新增哈希冲突次数 | 桶状态 |
---|---|---|
初始状态 | - | [], [], [], [], [] |
插入 |
0 | [], [], [2], [], [] |
插入 |
0 | [15], [], [2], [], [] |
插入 |
1 | [15], [], [2, 7], [], [] |
插入 |
2 | [15], [], [2, 7, 27], [], [] |
插入 |
0 | [15], [], [2, 7, 27], [8], [] |
插入 |
1 | [15, 30], [], [2, 7, 27], [8], [] |
请注意:交互库在每次你提交的时候都将 unordered_set
初始化为空集,然后把提交的数字依次插入来创建哈希表。也就是说,每一次的交互查询是相互独立的。
你的任务是使用不超过
实现细节
你需要实现以下函数:
int hack()
- 该函数返回一个整数
。 - 对于每个测试点,评测程序可能会调用该函数多于一次。每次调用都应该当做新的情况分别处理。
在这个函数中,你可能会调用以下交互函数:
long long collisions(std::vector<long long> x)
:一个包含不同整数的数组,其中对于所有 ,满足 。- 该函数返回一个整数,表示将数组
中所有元素依次插入哈希表引起的哈希冲突次数。 - 该函数可以多次调用。在一次
hack()
的调用中,多次调用的数组 的总长度不能超过 。
注意:由于 hack()
函数调用可能会发生多次,选手需要注意之前调用的残余数据对于后续调用的影响,尤其是全局变量的状态。
hack()
函数被调用了 hack()
时的花费不能超过
例子
假设有两组测试用例,评测程序将首先调用 hack()
函数:
hack()
在这个函数中,你可以进行以下调用:
函数调用 | 返回值 |
---|---|
collisions([2, 15, 7, 27, 8, 30]) |
4 |
collisions([1, 2, 3]) |
0 |
collisions([10, 20, 30, 40, 50]) |
10 |
如果你还原出 hack()
返回 5。
接下来,评测程序将再一次调用 hack()
函数:
hack()
在这个函数中,你可以进行以下调用:
函数调用 | 返回值 |
---|---|
collisions([1, 3]) |
1 |
collisions([2, 4]) |
1 |
你从上述调用中还原出唯一满足的 hack()
返回 2。
约束条件
,其中 为每组测试点中的测试用例数量。- 对于每次
collisions()
调用,
子任务
- (8 分)
- (17 分)
- (75 分) 没有额外的约束条件。
在最后一个子任务中,你可以获得部分分。令 hack()
函数中的最大总花费。该子任务的部分分计算如下:
条件 | 分数 |
---|---|
0 | |
75 |
在任意测试用例中,如果对 collisions()
函数调用不满足实现细节中的约束条件,或者 hack()
函数调用的返回值错误,该子任务的分数为 0。
评测程序示例
评测程序示例按以下格式读取输入:
- 第 1 行:
对于接下来
- 第 1 行:
对于每组测试用例,令 hack()
的返回值,
- 第 1 行: