#P13079. [NOISG 2019] Shuffle【交互题待配置】

    ID: 12879 Type: RemoteJudge 1000ms 256MiB Tried: 0 Accepted: 0 Difficulty: (None) Uploaded By: Tags>2019交互题NOISG(新加坡)

[NOISG 2019] Shuffle【交互题待配置】

题目描述

Lim Li 非常喜欢动漫,最近她在 Amazon 购买了一整季的《干物妹小埋》。这季共有 NN 集,每集刻录在一张光盘上,光盘编号为 11NN,每集的集数也是 11NN

然而,Lim Li 发现由于生产问题,光盘编号与剧集集数不对应!Amazon 告诉她,剧集只是被打乱顺序,所有剧集都在,没有缺失。

为了避免剧透,Lim Li 不愿自己播放光盘来确认剧集顺序。于是她决定请朋友 Rar the Cat 帮忙。具体流程如下:

  • Lim Li 将 NN 张光盘分为 BB 个盒子,每个盒子装 KK 张光盘(N=B×KN = B \times K)。
  • 这些盒子寄给 Rar。在运输过程中,盒子之间的顺序和每个盒子内部光盘的顺序可能会被打乱。
  • Rar 接收到盒子后,会播放每张光盘,并记录下盒子内各张光盘对应的剧集集数,然后将每个盒子的结果分别写在 BB 张纸上寄回给 Lim Li。
  • 所有光盘最终被寄回给 Lim Li。

整个过程最多允许进行 QQ 次。Rar 如果不耐烦就不再帮忙。

你的任务是,帮助 Lim Li 在尽量少的查询次数内,确定每张光盘上的剧集集数。

本题为交互题,请实现以下函数:

  • C++: vector<int> solve(int N, int B, int K, int Q, int ST)
  • Java: public int[] solve(int N, int B, int K, int Q, int ST)

你可以调用如下交互函数:

  • C++: vector<vector<int>> shuffle(vector<vector<int>> boxes)
  • Java: public static int[][] shuffle(int[][] boxes)

参数 boxesBB 个数组,每个数组包含 KK 个整数,表示 Lim Li 寄出的光盘编号分组。

返回值为 BB 个数组,每个数组 KK 个整数,表示收到盒子后,每张光盘的剧集集数。

注意:

  • boxes 传入参数不会被修改。
  • 超过 QQ 次调用或参数非法,判定为 Wrong Answer。

输入格式

所有必要信息通过函数参数提供。

输出格式

程序通过返回值完成答案,无需额外输出。

6 3 2 100 2
3 4 1 5 2 6

提示

【样例解释】

假设 N=6N = 6B=3B = 3K=2K = 2Q=100Q = 100,剧集顺序为 [3,1,4,5,2,6][3, 1, 4, 5, 2, 6]

调用 solve(6, 3, 2, 100, 2)

一次可能的交互:

  • 调用 shuffle([[1, 2], [3, 4], [5, 6]]),返回 [[6, 2], [5, 4], [3, 1]]
  • 调用 shuffle([[2, 6], [3, 1], [5, 4]]),返回 [[6, 1], [2, 5], [4, 3]]
  • 调用 shuffle([[6, 5], [4, 2], [3, 1]]),返回 [[5, 1], [3, 4], [2, 6]]

最终确定顺序为 [3,4,1,5,2,6][3, 4, 1, 5, 2, 6],输出该数组即为正确答案。

【数据范围】

  • B,K2B, K \geq 2
  • N6N \geq 6
  • N=B×KN = B \times K
子任务编号 分值 额外限制
11 22 N=6, B=2, K=3, Q=100N = 6,\ B = 2,\ K = 3,\ Q = 100
22 33 N=6, B=3, K=2, Q=100N = 6,\ B = 3,\ K = 2,\ Q = 100
33 1212 N1000, Q=12N \leq 1000,\ Q = 12,盒子顺序保持不变
44 1616 N1000, K=2, Q=4N \leq 1000,\ K = 2,\ Q = 4
55 1515 N1000, B=2, Q=12N \leq 1000,\ B = 2,\ Q = 12
66 5252 N1000, Q=2000, B,K>2N \leq 1000,\ Q = 2000,\ B,K > 2,具体见评分规则

【评分规则】

对于子任务 6,根据查询次数 qq 计分:

  • q>2000q > 2000,得 00 分;
  • 500<q2000500 < q \leq 2000,得 88 分;
  • 50<q50050 < q \leq 500,得 1717 分;
  • 9<q509 < q \leq 50,得 22+30×(50q41)222 + 30 \times \left(\dfrac{50 - q}{41}\right)^2 分;
  • q9q \leq 9,得 5252 分。

【测试说明】

官方提供裁判程序、头文件、模板与样例测试数据。请严格使用官方提供的测试脚本。