UOJ Logo Universal Online Judge

UOJ

#531. 【美团杯2020】最长公共子序列

统计

蒜斜和镁团在玩一个叫做“你问你猜”的游戏(可怜去哪了?)。规则如下:

镁团手中有$n$个数,且恰好是 $1-n$ 的排列。 每次询问,蒜斜需要给出一个长度不超过 $100$,且每个元素都在 $1-n$ 之间的数列(不需要是排列);之后镁团会告诉蒜斜这两个数列的最长公共子序列长度。 蒜斜需要在不超过$650$次询问内猜出镁团手中的排列。

这对于蒜斜来说实在太困难了,因此他找到了玉树临风文质彬彬英俊潇洒神采奕奕温文尔雅风度翩翩的你,你能帮助他吗?

任务

你需要编写一个函数 find_permutation,以确定镁团手中的排列是什么。

  • find_permutation(n, res)
    • n: 镁团手中排列的长度。
    • res:返回数组,你需要把你确定的排列存储到 res 中。

你可以调用函数 get_lcs 以帮助你确定镁团手中的排列。我们会根据你调用这个函数的次数评分。

  • get_lcs(len, A) 接受整数 len 和一个长度为 len 的数组 A,并会返回数组 A 与目标排列的最长公共子序列长度。

在一组测试数据中,find_permutation 只会被调用一次。

实现细节

本题只支持 C++。

你只能提交一个源文件实现如上所述的 find_permutation 函数,并且遵循下面的命名和接口。

C++

你需要包含头文件 lcs.h

void find_permutation(int n, int res[]);

你需要把答案排列存储在 res[0]res[n-1] 中。

函数 get_lcs 的接口信息如下。

int get_lcs(int len, int A[]);

你需要把询问的数组存储在 A[0]A[len-1] 中,数组 A 中的元素必须是区间 $[1,n]$ 中的整数。请保证你的所有询问都满足这个要求,不然的话可能会出现包括但不限于 Wrong Answer, Dangerous Syscalls 的评测错误。

如果有不清楚的地方,见样例及测评库下载,内附了样例程序

评测方式

评测系统将读入如下格式的输入数据:

  1. 第 $1$ 行: $n$,表示镁团手中的排列长度。
  2. 第 $2$ 行: $n$ 个空格隔开的整数,表示镁团手中的排列。

find_permutation 返回后,评测系统将输出你的答案以及 get_lcs 的调用次数。

样例输入

样例一

input

5
1 5 2 4 3

output

1 5 2 4 3
10

explanation

样例输出的含义为 find_permuation 在 $10$ 次询问之后,确定了镁团手中的排列为 $1\ 5\ 2\ 4\ 3$。

限制与约定

find_permutation 只能进行不超过 $650$ 次询问。如果超过了这个询问数量,你的程序将无法得分。

本题严禁任何形式的攻击交互库的行为,一旦发现,将取消相关选手的参赛资格。

Small Task: $n \leq 30$

Large Task: $n \leq 100$

时间限制:$1\texttt{s}$

空间限制:$256\texttt{MB}$

下载

样例交互库下载