QOJ #10977. Hidden Sequence Rotation 题解

Description

这是一个交互题（即你的程序需要通过标准输入/输出与评测器交互）。

你将得到一个整数 $N$。评测器内部维护了一个长度为 $N$ 的隐藏序列 $A = (A_0, A_1, \dots, A_{N-1})$，其中每个元素都是介于 $1$ 到 $10^5$ 的整数。

注意： 题目中所有的数组下标都是从 0 开始的。

对于任意的 $s = 0, 1, \dots, N-1$ 和 $l = 1, 2, \dots, N$，我们定义一个序列 $A(s, l)$，如下：

• $A(s, l)$ 是一个长度为 $l$ 的序列，它的第 $i$ 个元素是 $A_{(s+i)\bmod N}$，即从位置 $s$ 开始，按模 $N$ 循环地取 $l$ 个元素。

你最多可以向评测器提出 20 次查询，每次查询的格式如下：

• 你输出一组整数对 $((s_0, l_0), (s_1, l_1), \dots, (s_{k-1}, l_{k-1}))$，必须满足以下约束条件：

  • $1 \leq k \leq N$
  • $0 \leq s_i \leq N - 1$
  • $1 \leq l_i \leq N$
  • $\sum_{i=0}^{k-1} l_i \leq N$

评测器会返回一组下标 $i$（满足 $0 \leq i < k$），表示这些 $A(s_i, l_i)$ 中字典序最小的那些。也就是说，它返回的是集合：

$$\left\{i \mid A(s_i, l_i) = \min_{0 \leq j < k} A(s_j, l_j) \right\}$$

你需要通过最多 20 次这样的查询，找出所有满足 $A(s, N)$ 在所有 $A(s', N)$ 中字典序最小的 $s$，即：

$$\left\{s \mid 0 \leq s < N,\ A(s, N) = \min_{0 \leq s' < N} A(s', N) \right\}$$

$1\leq n\leq 10^5$。

Solution

首先如果给定 $a$ 序列，很容易想到倍增进行排序。

即假设现在已经求出满足 $A(i,len)$ 最小的坐标后，设其为 $i_1,i_2,\ldots,i_k$，现在只需要再求出 $i_1+len,i_2+len,\ldots,i_k+len$ 的最小坐标后就可以得到 $2\cdot len$ 的坐标。

回到这题，同样的，先询问一遍 $(0,1),(1,1),\ldots,(n-1,1)$ 后可以得到 $len=1$ 的最小坐标。

然后每次按照上面的那个做法询问 $(i_j+len,len)$ 的结果进行倍增。但是这么做 $\sum l_i$ 的长度和可能大于 $n$。

注意到如果 $[i_j,i_j+len-1]$ 和 $[i_{j+1},i_{j+1}+len-1]$ 有交，则 $d=i_{j+1}-i_j$ 一定是 $len$ 的因数，且一定存在一个最小下标是 $i_j+len-d$。

容易发现如果把相邻有交的区间连一条边，如果只有一个连通块，则说明已经排序好了，因为序列周期已经找到了。否则只有每个连通块最左边的区间可能成为答案，感性理解这是对的。

所以只有 $i_j-i_{j-1}\geq k$ 的下标需要询问，长度之和也就控制在了 $n$ 以内。

总次数显然是 $\log n$。

Code

#include <bits/stdc++.h>

// #define int int64_t

const int kMaxN = 1e5 + 5;

int n;

std::vector<int> ask(std::vector<int> &a, int len) {
  std::cout << "? " << a.size() << '\n';
  for (auto x : a) std::cout << x << ' ' << len << '\n';
  std::cout.flush();
  std::vector<int> v;
  int k;
  std::cin >> k;
  for (int i = 1; i <= k; ++i) {
    int x;
    std::cin >> x;
    v.emplace_back(a[x]);
  }
  return v;
}

void dickdreamer() {
  std::cin >> n;
  std::vector<int> a;
  for (int i = 0; i < n; ++i) a.emplace_back(i);
  a = ask(a, 1);
  for (int len = 1; len <= n; len <<= 1) {
    if (a.size() == 1) break;
    std::vector<int> tmp;
    for (int i = 0; i < a.size(); ++i) {
      if (i && a[i] - a[i - 1] > len || !i && a[i] - a.back() + n > len)
        tmp.emplace_back((a[i] + len) % n);
    }
    if (!tmp.size()) break;
    a = ask(tmp, len);
    for (auto &x : a) x = (x - len + n) % n;
  }
  std::cout << "! " << a.size() << '\n';
  for (auto x : a) std::cout << x << '\n';
}

int32_t main() {
#ifdef ORZXKR
  freopen("in.txt", "r", stdin);
  freopen("out.txt", "w", stdout);
#endif
  std::ios::sync_with_stdio(0), std::cin.tie(0), std::cout.tie(0);
  int T = 1;
  // std::cin >> T;
  while (T--) dickdreamer();
  // std::cerr << 1.0 * clock() / CLOCKS_PER_SEC << "s\n";
  return 0;
}