#PAPIO2022C. 排列

排列

题目描述

本题仅允许提交 C++17(O2) 代码。

法老们利用行星的引力来加速飞船。假设飞船将依次以 p[0],p[1],,p[n1]p[0], p[1],\dots , p[n - 1] 的轨道速度飞掠 nn 颗行星。飞掠每颗行星时,法老科学家可以选择是否利用它来加速飞船。为了节省能量,当飞船以轨道速度 p[i]p[i] 飞掠一颗行星并完成加速后,它将不能再在以轨道速度 p[j]<p[i]p[j] < p[i] 飞掠行星时进行加速。也就是说,选择用来加速的行星构成 p[0],p[1],,p[n1]p[0], p[1], \dots, p[n - 1] 的一个递增子序列pp 的子序列是从 pp 中删除零个或多个元素得到的序列。例如,[0][0][][ ][0,2][0, 2][0,1,2][0, 1, 2][0,1,2][0, 1, 2] 的子序列,但 [2,1][2, 1] 不是。

科学家已经确认,总共有 kk 种方案来选择行星对飞船进行加速,但是他们弄丢了轨道速度的记录信息(甚至包括 nn 的大小)。不过他们记得 (p[0],p[1],,p[n1])(p[0], p[1],\dots , p[n - 1])0,1,,n10, 1,\dots , n - 1 的一个排列。这里的排列是包含从 00n1n - 1 每个整数恰好一次的序列。 你的任务是找出一个长度尽量小且符合要求的排列 (p[0],p[1],,p[n1])(p[0], p[1],\dots , p[n - 1])

你要对 qq 艘不同的飞船来解决该问题。对每艘飞船 ii,你会得到一个整数 kik_i,表示选择行星加速飞船的不同方案数。你的任务是找出长度 nn 足够小的轨道速度序列,使得从中恰好可以选出 kik_i 个轨道速度递增的行星子序列。

实现细节

请在程序开头引入库 perm.h。你要实现以下函数:

int[] construct_permutation(int64 k);
  • kk 是应有的递增子序列的数量。
  • 该函数要返回有 nn 个元素的数组,每个元素是 00n1n - 1 之间(包括 00n1n - 1)的数。
  • 返回的数组必须是恰好有 kk 个递增子序列的合法排列。
  • 该函数总共被调用 qq 次。每次调用被视为一个独立的场景。

例 1

考虑以下调用:

construct_permutation(3);

该函数应该返回一个恰好有 33 个递增子序列的排列。一种可能的答案是 [1,0][1,0],它的递增子序列有 [][](空的子序列)、[0][0][1][1]

例 2

考虑以下调用:

construct_permutation(8);

该函数应该返回一个恰好有 88 个递增子序列的排列。一种可能的答案是 [0,1,2][0,1,2]

约束条件

  • 1q1001\le q\le 100
  • 2ki10182\le k_i\le 10^{18}(对所有 0iq10\le i\le q-1)。

子任务

  1. 1010 分)2ki902\le k_i\le 90(对所有 0iq10\le i\le q-1)。如果你给出的所有排列长度至多为 9090 且结果正确,你将获得 1010 分,否则获得 00 分。
  2. 9090 分)没有额外的约束条件。对该子任务,令 mm 为你在所有场景中给出的排列的最大长度,则你的得分按下表来计算:
条件 得分
m90m\le 90 9090
90<m12090 < m\le 120 90m90390-\dfrac{m-90}{3}
120<m5000120 < m\le 5000 80m1206580-\dfrac{m-120}{65}
m>5000m > 5000 00

评测程序示例

评测程序示例按以下格式读取输入:

  • 11 行:qq
  • 2+i2+i 行(0iq10\le i\le q-1):kik_i

评测示例程序对每个 kik_i 打印一行,包含对应 construct_permutation 调用的返回值。如果出错则打印错误信息。