#3364. 「IOI2020」植物比较

内存限制:1024 MiB 时间限制:4000 ms 题目类型:交互
上传者: EntropyIncreaser

题目描述

注意:在 LibreOJ 上,由于语言限制,目前只支持以下语言的提交:

  • C++ 11
  • C++ 11 (Clang)
  • C++ 11 (NOI)
  • C++ 17
  • C++ 17 (Clang)

植物学家 Hazel 参观过新加坡植物园的一个特别展览。在这次展览中,有 n 棵高度互不相同的植物,它们排成了一个圆。这些植物按顺时针方向从 0 n-1 编号,植物 n-1 与植物 0 是相邻的。

对于每棵植物 i\ (0\le i\le n-1 ) ,Hazel 将它与顺时针方向的后 k-1 棵植物进行比较,记录下数值 r_i 以表示这 k-1 棵植物中有多少棵的高度大于植物 i 。因此,每个 r_i 的数值是由某段连续 k 棵植物的相对高度决定的。

例如,假设 n=5 k=3 i=3 。植物 3 顺时针方向的后 k-1=2 棵植物是植物 4 和植物 0 。如果植物 4 比植物 3 高,且植物 0 比植物 3 矮,那么 Hazel 将会记录 r_3 = 1

你可以假设 Hazel 记录的数值 r_i 都是正确的。也就是说,这些植物至少存在一组互不相同的高度符合 Hazel 所记录的数值。

本题要求你比较 q 对植物的高度。由于你没有机会参观这次展览,你仅有的信息来源是 Hazel 的笔记本,其中记录了 k 和序列 r_0,\ldots, r_{n-1} 的值。 对于每对需要比较的植物 x y x y 不同),判定它们符合以下哪种情况:

  • 植物 x 一定比植物 y 高:对于任意一组符合数组 r 且互不相同的高度 h_0,\ldots h_{n-1} ,都有 h_x>h_y
  • 植物 x 一定比植物 y 矮:对于任意一组符合数组 r 且互不相同的高度 h_0,\ldots h_{n-1} ,都有 h_x<h_y
  • 该比较没有定论:以上两种情况都不成立。

实现细节

要求你实现以下函数:

void init(int k, int[] r)
  • k :决定每个 r_i 数值的连续植物的棵数。
  • r :一个大小为 n 的数组,其中 r_i 是植物 i 顺时针方向的后 k-1 棵植物中比它高的棵数。
  • 该函数恰好被调用一次,且在对 compare_plants 的任何调用之前。
int compare_plants(int x, int y)
  • x,y :待比较的植物的编号。
  • 该函数应该返回:
    • 1 :如果植物 x 一定比植物 y 高,
    • -1 :如果植物 x 一定比植物 y 矮,
    • 0 :如果该比较没有定论。
  • 该函数恰好被调用 q 次。

评测程序示例

评测程序示例以如下格式读取输入数据:

  • 1 行: n\ k\ q
  • 2 行: r_{0}\ r_{1}\ \ldots\ r_{n-1}
  • 3+i\ (0\le i\le q-1) 行: x\ y ,表示第 i 次调用 compare_plants 时的参数

评测程序示例以如下格式打印你的答案:

  • 1+i\ (0\le i\le q-1) 行: 第 i 次调用 compare_plants 的返回值

样例

样例输入 1

4 3 2
0 1 1 2
0 2
1 2

样例输出 1

1
-1

样例说明 1

考虑以下调用:

init(3, [0, 1, 1, 2])

假设评测程序调用了 compare_plants(0, 2)。由 r_0=0 可以推断植物 2 不比植物 0 高,因此该调用应该返回 1

假设评测程序接下来调用了 compare_plants(1, 2)。由于对每组符合以上条件的植物高度,都有植物 1 比植物 2 矮,因此该调用应该返回 -1

样例输入 2

4 2 2
0 1 0 1
0 3
1 3

样例输出 2

1
0

样例说明 2

考虑以下调用:

init(2, [0, 1, 0, 1])

假设评测程序调用了 compare_plants(0, 3)。由 r_3=1 可以推断植物 0 比植物 3 高,因此该调用应该返回 1

假设评测程序接下来调用了 compare_plants(1, 3)。两组高度 [3,1,4,2] [3,2,4,1] 都符合 Hazel 的观测记录,由于在第一种情况中植物 1 比植物 3 矮,而在第二种情况中它比植物 3 高,因此该调用应该返回 0

数据范围与提示

对于 100\% 的数据,满足:

  • 2\le k\le n\le 200\ 000
  • 1\le q\le 200\ 000
  • 0\le r_i\le k-1 (对所有 0\le i\le n-1
  • 0\le x<y\le n-1
  • 存在一组或多组互不相同的高度符合数组 r 记录的情况
子任务 附加限制 分值
1 k=2 5
2 n\le 5000, 2\cdot k>n 14
3 2\cdot k>n 13
4 每次 compare_plants 调用的正确答案是 1 -1 17
5 n\le 300, q\le \frac{n\cdot (n-1)}{2} 11
6 每次调用 compare_plants 时有 x=0 15
7 没有附加约束条件 25