自动搬运

查看原文

来自洛谷，原作者为

	EuphoricStar Remember.

搬运于2025-08-24 22:25:28，当前版本为作者最后更新于2023-11-09 14:45:25，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

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$。实际会略大，但是能过。

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);
}