#P9696. duyi 的切题树

    ID: 6316 交互题 12000ms 512MiB 尝试: 3 已通过: 1 难度: 9 上传者: 标签>难度分类省选/NOI-交互与信息策略自适应查询树算法LCA枚举与搜索深度优先搜索动态规划线性 DPCF2600树论

duyi 的切题树

duyi 的切题树(tree)

题目类型

函数式交互题。

你需要使用下发的头文件 tree.h,并实现指定函数。评测过程中不使用传统的标准输入、标准输出交互方式。

题目描述

duyi 有一棵“切题树”。这棵树是一棵高度为 nn 的满二叉树,根节点的高度为 11,因此整棵树共有

2n−12^n-1

个节点。

duyi 有 2n−12^n-1 道要切的题。为了便于辨认,这些题被编号为

1,2,…,2n−1.1,2,\ldots,2^n-1.

每天,duyi 会使用随机数生成器生成一个排列,并按照该排列的顺序,将所有题目依次放入树中。保证每个节点恰好放置一道题。随后,duyi 会切掉位于根节点上的题目。

你获得了接下来 1000010000 天的随机顺序。对于每一天,你需要找出位于根节点上的题目编号。

为了确定答案,每一天你最多可以进行 SS 次询问。每次询问指定一道题的编号,系统会返回这道题所在节点的所有相邻节点上放置的题目编号。

交互接口

本题不使用传统文件输入输出。

你需要在程序开头包含头文件:

#include "tree.h"

头文件中提供如下询问函数:

std::vector<int> query(int x);

调用 query(x) 后,评测库会返回一个 std::vector<int>,其中包含编号为 xx 的题目在树中的所有相邻节点上放置的题目编号。

返回的所有编号均位于区间

[1,2n−1][1,2^n-1]

内,并且互不相同。

每次调用 query 时,你传入的参数也必须满足

1≤x≤2n−1.1\le x\le 2^n-1.

否则该次评测将被判为 Wrong Answer。

你需要实现如下函数:

int solve(int n);

其中,参数 nn 表示满二叉树的高度。函数返回值应为当天位于根节点上的题目编号。

对于每个子任务,可能包含若干个测试点。对于每个测试点,评测库会调用 solve 函数 1000010000 次。只有全部调用均正确,该测试点才能获得满分。

注意:如果程序中使用了自定义全局变量,需要在每次调用 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 次调用且没有越界/超限/额外输出才通过。配置中的输出文件仅为接口占位,真实答案由交互器核验。

数据范围与约定

记 SS 为每一天允许进行的最大询问次数。

对于所有数据:

1≤n≤12.1\le n\le 12.
子任务 分值 限制
1 1010 S=4095S=4095
2 1515 S=100S=100
3 55 n=3, S=3n=3,\ S=3
4 1010 n=4, S=5n=4,\ S=5
5 S=60S=60
6 2020 S=51S=51
7 3030 S=50S=50

原题面