UOJ Logo Universal Online Judge

UOJ

#1118. 【UER #14】果冻

附件下载 统计

本题为交互题。

在跳蚤甜品店的柜台上,摆放着两排色彩缤纷的双层果冻(上层为 $a$,下层为 $b$)。由于店内的“凝固互补”规则,每组果冻上层与下层的高度之和恰好为 $n+1$。原本店员已经将这两排果冻按高度排成了 $1 \sim n$ 的完美排列,但在昨晚,活泼的跳蚤店员不小心将某些位置的上下层果冻给颠倒了!

现在,一年一度的甜品节马上就要开幕,店员们必须还原出果冻颠倒前的初始摆放状态(即颠倒前的上层果冻高度序列 $a$)。

你无法直接观察果冻的高度,但你可以向甜品店的自动测量仪发出指令:指定若干个位置 $i$,测量仪会帮你翻转这些位置的上下层果冻,并返回当前上层果冻的最大高度与最小高度之差(极差),以及下层果冻的最大高度与最小高度之差(极差)。注意:每次翻转的操作都会保留。

你能否在有限的翻转测量次数内,成功还原出最初的上层果冻摆放序列呢?


交互库先选定一个 $1\sim n$ 的排列 $p$,构造排列 $b_i=n+1-p_i$。然后,对于每个下标 $i$,交互库独立决定是否交换位置 $i$ 的两个数。将交换完成后得到的数组记为 $a,b$。此时总有 $a_i+b_i=n+1$,但 $a,b$ 不一定仍是排列。

你知道 $n$,却不知道这两个数组。你可以选择若干位置,交换这些位置的 $a_i,b_i$;交互库会告诉你交换后两个数组的极差。每次交换的效果都会保留。

你的任务是还原第一次询问之前的数组 $a$。若将返回数组的每个值 $x$ 同时替换为 $n+1-x$ 后才与目标相同,也认为答案正确。

实现细节

选手不需要,也不应该实现 main 函数。

选手需要在源文件 recover.cpp 中包含头文件 range.h,并实现以下函数:

std::vector<int> recover(int c, int n);
  • $c$ 为当前子任务编号,正式测试中取 $1,2,3,4$;样例中取 $0$。$n$ 为数组长度。交互库对每个测试点恰好调用一次 recover。
  • 返回值必须是长度为 $n$ 的整数数组,表示第一次询问之前的 $a$,或它的整体取补。

选手可以调用以下函数:

std::pair<int, int> query(const std::vector<int>& positions);
  • positions 中的下标必须两两不同,且属于 $[0,n-1]$。允许传入空数组。
  • 交互库按 positions 中的下标各交换一次当前的 $a_i,b_i$,然后返回当前 $a$ 的极差与当前 $b$ 的极差。询问之间的交换会累积,但返回答案时应还原交换前的初始数组。
  • 极差定义为数组最大值减去最小值。由于始终有 $b_i=n+1-a_i$,两个极差一定相等。
  • query 的调用次数不能超过所在测试点的上限 $Q_{\max}$。

交互库不是适应性的:初始数组在 recover 开始前已经确定,不会随选手的询问改变。最终评测使用的交互库与下发的样例交互库可能不同,选手程序不得读取交互库内部数据或直接操作标准输入、输出流。

测试程序方式

把 recover.cpp、range.h 和附件中的 grader.cpp 放在同一目录,使用 C++17 编译:

g++ grader.cpp recover.cpp -o recover -O2 -std=c++17
./recover < ex_range1.in

本地交互库读入的第一行是 $c,n,Q_{\max}$;第二行是排列 $p_0,\ldots,p_{n-1}$;第三行是 $n$ 个 $0/1$ 数,其中 $1$ 表示交互开始前交换该位置。只有 $c,n$ 会通过函数参数提供给选手;排列、交换标记和询问上限不会直接传给选手程序。

若答案正确,本地交互库输出第一行 Correct!,第二行 Queries used: Q,其中 $Q$ 是本次调用中使用的询问次数。若答案错误,则输出 Wrong answer.;若接口调用不合法,还会在标准错误流给出错误原因。

样例一

input

0 6 67
3 1 6 4 2 5
0 1 1 0 1 0

output

Correct!
Queries used: 16

explanation

样例中,交互开始前的 $a=(3,6,1,4,5,5)$;其整体取补为 $(4,1,6,3,2,2)$。返回其中任意一个都正确。第一次调用 query({}) 返回 $(5,5)$。上述输出对应附件中的标准程序运行结果;不同正确程序的询问次数可能不同。

数据范围

对于所有测试数据,$1\le n\le 500$。

子任务 分值 $n \le$ $Q_{\max} = $ 特殊性质
$1$ $10$ $20$ $50000$ 无
$2$ $10$ $100$ $21000$ 无
$3$ $40$ $500$ $50000$ 保证初始 $a$ 为 $1 \sim n$ 的排列
$4$ $40$ $500$ $50000$ 无

每个子任务按其中得分倍率最低的测试点计分,具体见下文。

评分方式

若 recover 返回的答案不正确、query 的参数不合法,或询问次数超过 $Q_{\max}$,该测试点得分为 $0$。

否则,对于子任务 $1,2$,该测试点获得全部分数。对于子任务 $3,4$,设 $Q$ 为该测试点实际使用的询问次数,得分倍率 $f(Q)$ 按下表计算:

$Q$ 的范围 $f(Q)$
$Q\le5000$ $1$
$5000 < Q\le10000$ $1-\dfrac{Q-5000}{20000}$
$10000 < Q\le20000$ $\dfrac34-\dfrac{Q-10000}{40000}$
$20000 < Q\le50000$ $\dfrac12-\dfrac{Q-20000}{100000}$
$Q>50000$ $0$
$Q$ 不超过 $5000$ $10000$ $20000$ $50000$ 超过 $50000$
$f(Q)$ $100\%$ $75\%$ $50\%$ $20\%$ $0\%$

子任务 $3$ 的得分为 $40f(Q)$,子任务 $4$ 的得分为 $40f(Q)$。最终得分按小数点后 $3$ 位四舍五入。

时间限制:$2\ \mathrm{s}$。

空间限制:$512\ \mathrm{MiB}$。