NOIP 模拟赛 T2。随机化交互好题。
令 \(a\) 为原题面中的 \(e\)，\(b\) 为原题面中的 \(o\)。
显然可以使用 \(\left\lceil\frac{n}{2}\right\rceil\) 次询问求出 \(a\) 中任意其中一个元素的值，全部问一遍 \(a_i\) 和 \(b_j\) 的大小关系即可。但是这样很浪费。
考虑我们求出了一个 \(a_i\)，我们还知道了所有 \(b_j\) 和这个 \(a_i\) 的大小关系。那么经过这 \(n\) 次询问后，\(b\) 被分成了两个值域的“块”，我们知道两个块的值域的 \([l, r]\) 和它们包含哪些位置。
那么当我们求每一个 \(a_i\)，\(b\) 中的一个块会分成两个，除非 \(n\) 为偶数且 \(a_i = n\)，这种情况特判即可。通过二分我们可以知道 \(a_i\) 可能在哪两个块中。二分 check 时和块内任意一个 \(b_j\) 比较即可。得到这两个块后，暴力把块中每个元素都比较一遍，就可以把其中一个块分成两个，同时也能知道 \(a_i\) 的值。
现在问题是询问次数没有保证。考虑以一个随机的顺序问 \(a_i\)，问完 \(i\) 个 \(a\) 后每个块的期望大小约为 \(\frac{n}{2i}\)，暴力问两个块，最坏就是期望问 \(\frac{n}{i}\) 次。再加上二分的次数 \(\sum\limits_{i = 1}^n \log_2i\)，\(n = 10000\) 时期望询问次数约为 \(1.45 \times 10^5\)。实际会略大，但是能过。
code
const int maxn = 10050;
int n, a[maxn], b[maxn], p[maxn];
struct node {
int l, r;
vector<int> ps;
};
void solve(int _n) {
n = _n;
node u;
u.l = 1;
u.r = (n + 1) / 2 * 2 - 1;
for (int i = 1; i <= (n + 1) / 2; ++i) {
u.ps.pb(i);
}
vector<node> vc;
vc.pb(u);
mt19937 rnd(chrono::steady_clock::now().time_since_epoch().count());
for (int i = 1; i <= n / 2; ++i) {
p[i] = i;
}
shuffle(p + 1, p + n / 2 + 1, rnd);
for (int i = 1; i <= n / 2; ++i) {
int l = 0, r = (int)vc.size() - 1;
while (r - l + 1 > 2) {
int mid = (l + r) >> 1;
if (ask(p[i], vc[mid].ps[0])) {
l = mid;
} else {
r = mid;
}
}
bool flag = 1;
for (int j = l; j <= r; ++j) {
vector<int> v1, v2;
for (int x : vc[j].ps) {
if (ask(p[i], x)) {
v1.pb(x);
} else {
v2.pb(x);
}
}
if (v1.empty() || v2.empty()) {
continue;
}
flag = 0;
if (j) {
a[p[i]] = vc[j - 1].r + 1;
}
a[p[i]] += (int)v1.size() * 2;
node u;
u.l = a[p[i]] + 1;
u.r = vc[j].r;
vc[j].r = a[p[i]] - 1;
vc[j].ps = v1;
u.ps = v2;
vc.insert(vc.begin() + j + 1, u);
break;
}
if (flag) {
a[p[i]] = n;
}
}
for (node u : vc) {
b[u.ps[0]] = u.l;
}
vector<int> v1, v2;
for (int i = 1; i <= n / 2; ++i) {
v1.pb(a[i]);
}
for (int i = 1; i <= (n + 1) / 2; ++i) {
v2.pb(b[i]);
}
report(v1, v2);
}