Statement

给出 $n$，交互库初始拥有一个 $0 \sim n - 1$ 的排列 $p_1, p_2, ..., p_n$。你每次可以调用一个函数 $f(l, r)$，其中 $f(l, r)$ 的定义如下：

• $|p_r - p_l| = 1$：此时交互库会返回 $[p_l < p_r]$。

• $|p_r - p_l| \ne 1$：此时交互库会返回 $[p_l > p_r]$。

要求你在 $10000$ 次询问内还原该序列。$n \le 1000$。

自己写的交互库 no adaptive。

Solution

讲一下思考过程。

称 $i$ 可以打败 $j$ 当且仅当 $f(i, j) = 1$。

先考虑 $n^2$ 的暴力如何做：对于每个 $i$，求出 $rk_i = \sum_{i = 0}^{n - 1}[i \ne j] f(i, j)$。那么不难发现除了在排列中除了 $p_i = 0/n - 1$ 的位置 $i$ 都有 $p_i = rk_i$，这是因为对于一个 $i$，若 $i - 1, i + 1$ 均存在，那么此时 $i$ 可以打败 $i + 1$，而不能打败 $i - 1$，两者算错的贡献恰好抵消了。而对于 $p_i = 0$，我们会算出来 $rk_i = 1$，因此 $rk$ 中会有两个 $1$，多比较一次即可算出哪个是真正的 $1$。对于 $rk_i = n - 2$ 的同理算出哪个才是真正的 $n - 2$。那么此时我们有了 $\frac{(n - 1)n}{2} + 2$ 次数的做法。

10pts 代码。

我们考虑如何优化。发现本质上我们要求的东西就是一个值的排名，那么我们直接排个序，这样是不是就做完了？实则并非，考虑如下样例：

5
1 0 2 4 3

手玩一下你会发现，在上面这个样例中，对于每一个 $p_{i + 1}$ 都可以打败 $p_i$，但是写出 $rk$ 数组发现完全是错的。而且假如你写了把 query 作为 cmp 传入 sort 中来排序，你会发现交上去 RE 了。这两个的具体原因都是，这些大小关系并不满足传递性，换句话说，假设 $i$ 可以打败 $j$ 就连边 $i \to j$，则该图中有若干三元环 $x - 1\to x\to x + 1 \to x - 1$。

下面设排好序的（下标）序列为 $id_0, id_1, ..., id_{n - 1}$，此时满足 $\forall 0 \le i \le n - 2,f(id_i, id_{i + 1}) = 1$，同时设 $p'_i = p_{id_i}$。

但是当我们研究完这个冲突的本质后，我们发现，$p'_i,p'_{i + 1}$ 一定满足 $p'_i < p'_{i + 1}$ 或者 $p'_i = p'_{i + 1} + 1$。对着这个东西再想一想，发现我们可以将 $p'$ 划分为若干个在下标上和值域上均连续的一些区间。形式化的，我们可以将 $p$ 划分为若干个区间 $[l_1, r_1], [l_2, r_2], [l_3, r_3]..., [l_m, r_m]$，且满足以下性质：

• $\forall i \in [1, m], j \in [l_i, r_i)$，有 $p'_{j} = p'_{j + 1} + 1$。

• $\forall i \in [1, m)$，有 $l_i = r_{i - 1} + 1, p'_{r_i} = p'_{l_{i - 1}} + 1$。

那么问题转化为求出所有的区间，考虑增量法。假设我们求出了上一个区间 $[l_{i - 1}, r_{i - 1}]$，则 $l_i = r_{i - 1} + 1$，然后我们对于 $j \ge l_i$ 逐个判定 $j$ 是否是当前区间的元素。但是这样不是很好做，不妨转化一下，判断 $j$ 是否为当前区间的结尾。那么根据 $p'_{r_i} = p'_{l_i} + 1$ 以及 $j \ge l_i$，我们可以发现，当且仅当 $j = r_i$ 时，$f(id_{l_{i - 1}}, id_j) = 1$。依赖这个性质，我们就可以求出除了第一个以外的区间了。

那么如何求出第一个区间呢？注意到我们只需要求出 $p'_0$ 即可，那么直接使用暴力即可。同时注意求出来的 $p'_0 = 1/n - 2$ 的情况，由于我们的暴力不区分 $0/1, n-2/n-1$，此时需要再求出 $p'_1$ 才可以判断 $p'_0$ 到底是什么。

最劣查询次数是 $n \log n + 3n$。会略微会超过 $10000$ 一点点，但是由于取平均值的原因，依然可以获得 100 分。

100 pts 代码。

#include<bits/stdc++.h>
#define ll long long
#define pb emplace_back
#define pir pair<int, ll>
#define fi first
#define se second
#define inv(x) qpow(x, mod - 2)
#define il inline
#define mkpir make_pair
#define ull unsigned long long
#define umap unordered_map
using namespace std;

const int N = 1000 + 10, M = 2e5 + 10;
const ll mod = 998244353;

/*
struct edge{
  int v, next;
}edges[M << 1];
int head[N], idx;

void add_edge(int u, int v){
  edges[++idx] = {v, head[u]};
  head[u] = idx;
}
*/

il ll qpow(ll x, ll y){
  ll ret = 1;
  for(; y; y >>= 1, x = x * x % mod) if(y & 1) ret = ret * x % mod;
  return ret;
}
il void chkmin(ll& x, ll y){if(y < x) x = y;}
il void chkmax(ll& x, ll y){if(y > x) x = y;}
il void chkmin(int& x, int y){if(y < x) x = y;}
il void chkmax(int& x, int y){if(y > x) x = y;}
il void chkmod(ll& x){x = (x + mod) % mod;}
il void ADD(ll& x, ll y){x += y; (x >= mod) ? (x -= mod) : 0;}
il void MUL(ll& x, ll y){x = x * y % mod;}
//#define int long long

extern "C" bool Query(int a, int b);
int n, rk[N], id[N], tmp[N];

void mysort(int l, int r){
  if(l >= r) return;
  int mid = (l + r >> 1), j = mid + 1, now = l;
  mysort(l, mid); mysort(mid + 1, r);
  for(int i = l; i <= mid; i++){
    while(j <= r && Query(id[i], id[j])) tmp[now] = id[j], j++, now++;
    tmp[now] = id[i]; now++;
  }
  while(j <= r) tmp[now] = id[j], j++, now++;
  for(int i = l; i <= r; i++) id[i] = tmp[i];
}

// can't distinguish(?) 0 / 1, n - 2 / n - 1
int getid(int x){
  int gt = 0;
  for(int i = 0; i < n; i++) if(i != x) gt += Query(x, i);
  return gt;
}

vector<int> ans, res;

void solve(int st){
  int lstfir = 0, lst = st;
  for(int i = st; i < n; i++){
    if(!Query(id[i], id[lstfir])){
      int cnt = i;
      for(int j = lst; j <= i; j++) ans[j] = cnt, cnt--;
      lstfir = lst; lst = i + 1;
    }
  }
}

extern "C" std::vector<int> Solve(int N){
  bool dbg = 0;
  n = N; ans.resize(n); res.resize(n);
  for(int i = 0; i < n; i++) id[i] = i;
  mysort(0, n - 1);
  for(int i = 0; i < n; i++) ans[i] = id[i];
  if(dbg) return ans;
  
  // check
  //for(int i = 0; i < n; i++) cerr << id[i] << " "; cerr << "\n";
//  for(int i = 0; i < n - 1; i++) assert(Query(id[i + 1], id[i]));
  
  // solve
  int a0 = getid(id[0]);
  if(a0 == 1){
    if(getid(id[1]) == 1) ans[0] = 1, ans[1] = 0, solve(2);
    else ans[0] = 0, solve(1);
  } else if(a0 == n - 2){
    if(getid(id[1]) == n - 2){
      for(int i = 0; i < n; i++) ans[i] = n - i - 1;
    } else{
      for(int i = 0; i < n - 1; i++) ans[i] = n - i - 1;
      ans[n - 1] = n - 1; 
    }
  } else{
    for(int i = 0; i <= a0; i++) ans[i] = a0 - i;
    solve(a0 + 1);
  }
  for(int i = 0; i < n; i++) res[id[i]] = ans[i];
  return res;
}