logo AlgoBeat OnlineJudge
登录 注册

#214794. [RMI 2025] 猜排列 / Guess Permutation

内存限制:2048 MiB 时间限制:4000 ms 标准输入输出
题目类型:VJudge(洛谷) 评测方式:VJudge
上传者: 匿名

题目描述

不要引入头文件。在文件头粘贴

#include <vector>
int press_button(int);

以评测。


这是一道交互题。本题中,交互库是非自适应的。

有一台破旧的机器,有 隐藏的开关,编号 。开关的状态用 来表示。我们说开关 断开,当且仅当 ;否则 ,开关 接通

起初,所有开关都是断开的。

个按钮,编号 。有一个隐藏的 的排列,记为

现在想要确定 。为此,你可以进行如下的操作:

操作

  • 选定 满足 ,按下按钮
  • 令本次操作(不含本次)一共进行了 次操作。
  • 翻转开关 的状态。形式化地,令
  • 你将得知 的值。

给定 ,你需要用至多 次操作找出排列

为了获得满分,需要更少的操作次数,详见「计分方式」。

实现细节

这是一道(函数式)交互题。你不需要,也不应该定义 main 函数。

你需要实现函数

std::vector<int> solve(int N);

该函数接收参数 ;返回长度为 vector 满足 。该函数每个测试点仅调用一次。

你可以调用以下的函数:

int press_button(int i);

描述一次按下按钮 的操作,返回操作后 的值。

Sample Grader

在附件中附有 sample grader()。其输入格式如下:

  • 第一行:正整数
  • 第二行: 个整数

它会调用 solve(N) 函数,报告你程序的运行结果:若通过,输出查询次数;否则,输出错误信息。

输入格式

见「实现细节」。

输出格式

见「实现细节」。

数据范围与提示

样例解释

考虑 和以下的调用。

操作 返回值
返回

限制条件

  • 的排列。

子任务

# 得分

计分方式

如果你的程序未能成功结束,或者答案错误,得 分。

否则,令 为你的程序调用 press_button() 的次数。令 ,若 ,得 分。否则,每个子任务得分为系数 乘以子任务满分。 的计算方式如下:

  • 子任务
  • 子任务
  • 子任务

你可以利用下图获得直观感受。

::::align{center} ::::