#P11779. [COTS 2012] 宿舍移动 / BUKA

    ID: 13165 远端评测题 5000ms 256MiB 尝试: 0 已通过: 0 难度: 5 上传者: 标签>2012交互题Special JudgeCOCI(克罗地亚)

[COTS 2012] 宿舍移动 / BUKA

题目描述

本题为交互题。

有一棵 nn 个节点的有根满二叉树,若 n=1n=1 则根度数为 00 否则根度数为 22,每个点的编号未知。

你每次可以询问两个点 a,ba,b,交互库返回树上 aabb 的路径中离根最近的点的编号,你需要在 5×1045 \times 10^4 次询问内求出每个点的父亲。特别地,根的父亲为根。

交互方式

这是一道 IO 交互题,你需要从标准输入输出中与交互库交互。

首先,从标准输入中读取满二叉树点数 nn

然后,你可以进行不超过 5×1045 \times 10^4 次交互,形式为 pitaj a b,其中需要满足 1a,bn1 \leq a, b \leq n,交互库返回树上 aabb 路径中到根最近的点的编号。在你确定答案后,首先输出 kraj 并换行,然后输出 nn 行,第 ii 行表示编号为 ii 的点在二叉树上的父亲。

在每次询问后以及最终输出答案后,你需要刷新缓冲区。

输入格式

见「交互方式」。

输出格式

见「交互方式」。

提示

1n1041 \leq n \leq 10^4,保证 n=2k1n = 2^k-1kk 为正整数。