#P9696. duyi 的切题树
duyi 的切题树
duyi 的切题树(tree)
题目类型
函数式交互题。
你需要使用下发的头文件 tree.h,并实现指定函数。评测过程中不使用传统的标准输入、标准输出交互方式。
题目描述
duyi 有一棵“切题树”。这棵树是一棵高度为 的满二叉树,根节点的高度为 ,因此整棵树共有
个节点。
duyi 有 道要切的题。为了便于辨认,这些题被编号为
每天,duyi 会使用随机数生成器生成一个排列,并按照该排列的顺序,将所有题目依次放入树中。保证每个节点恰好放置一道题。随后,duyi 会切掉位于根节点上的题目。
你获得了接下来 天的随机顺序。对于每一天,你需要找出位于根节点上的题目编号。
为了确定答案,每一天你最多可以进行 次询问。每次询问指定一道题的编号,系统会返回这道题所在节点的所有相邻节点上放置的题目编号。
交互接口
本题不使用传统文件输入输出。
你需要在程序开头包含头文件:
#include "tree.h"
头文件中提供如下询问函数:
std::vector<int> query(int x);
调用 query(x) 后,评测库会返回一个 std::vector<int>,其中包含编号为 的题目在树中的所有相邻节点上放置的题目编号。
返回的所有编号均位于区间
内,并且互不相同。
每次调用 query 时,你传入的参数也必须满足
否则该次评测将被判为 Wrong Answer。
你需要实现如下函数:
int solve(int n);
其中,参数 表示满二叉树的高度。函数返回值应为当天位于根节点上的题目编号。
对于每个子任务,可能包含若干个测试点。对于每个测试点,评测库会调用 solve 函数 次。只有全部调用均正确,该测试点才能获得满分。
注意:如果程序中使用了自定义全局变量,需要在每次调用
solve时自行清空或重新初始化。
示例程序
下面是一份合法的程序,但它无法获得有效分数:
#include <bits/stdc++.h>
#include "tree.h"
using namespace std;
int solve(int n) {
vector<int> v = query(1);
return v.empty() ? 1 : v.back();
}
本地测试与 Hydro 提交
Hydro 版时限为 12 秒、内存为 512 MiB。原题进程内函数评测为 3 秒;本版为避免公开成功字串可被伪造,改用独立进程逐次核验,增加通信开销,因此单独调整运行时限。每天的询问次数上限、每点 10000 次调用和原七档分值均保持不变。
请使用 C++17 或更高版本,包含新版 tree.h,只实现 solve(int n);头文件提供程序入口,不要再编写 main 函数。也不要自行向标准输出写内容,头文件负责必要通信。邻居返回顺序不作保证。
每个测试点都会实际调用 solve 10000 次,每次调用的询问次数单独计算,开始下一天后预算重置。
下载 独立交互器、testlib.h、本地连接程序 及 测试输入。将这些文件与自己的 solution.cpp 放在同一目录后,可编译:
g++ -std=c++17 -O2 solution.cpp -o solution
g++ -std=c++17 -O2 interactor.cpp -o interactor
python tree_local_runner.py tree_sample.in --program ./solution --interactor ./interactor
Windows 下可以使用对应的 .exe 文件名。
交互器输入为一行 n S seed:树高 n、每天询问上限 S、范围为 0 到 4294967295 的随机种子。这个输入给交互器读取,选手程序通过接口交互。正确完成全部 10000 次调用且没有越界/超限/额外输出才通过。配置中的输出文件仅为接口占位,真实答案由交互器核验。
数据范围与约定
记 为每一天允许进行的最大询问次数。
对于所有数据:
| 子任务 | 分值 | 限制 |
|---|---|---|
| 1 | ||
| 2 | ||
| 3 | ||
| 4 | ||
| 5 | ||
| 6 | ||
| 7 |