CF1521C Nastia and a Hidden Permutation

发布于 2021-05-08  1.39k 次阅读


题面

题意

交互题。

交互库在开始时会生成一个长为 $n$ 的排列 $p$。你在开始时仅知道排列的长度 $n$,你需要在进行不超过 $\lfloor \frac {3 \times n} 2 \rfloor + 30$ 次询问后输出这个排列。

你可以进行两种类型的提问:

  1. ? 1 i j x: 交互库会告诉你 $\max(\min(x,p_i),\min(x+1,p_j))$ 的值。
  2. ? 2 i j x: 交互库会告诉你 $\min(\max(x,p_i),\max(x+1,p_j))$ 的值。

分析

我们考虑指定 $i,~j,~x$ 后所有可能的情况下的询问结果,为了方便归类,下面忽略了相等的情况。

  1. $p_i >x,~p_j>x+1$: $1$ 询问返回 $x+1$,$2$ 询问返回 $\min(p_i,p_j)$。
  2. $p_i>x,~p_j<x+1$: $1$ 询问返回 $x$,$2$ 询问返回 $x+1$。
  3. $p_i<x,~p_j>x+1$: $1$ 询问返回 $x+1$,$2$ 询问返回 $x$。
  4. $p_i<x,~p_j<x+1$: $1$ 询问返回 $\max(p_i,p_j)$,$2$ 询问返回 $x$。

我们发现这四种情况中仅 $1$ 情况的 $2$ 询问,和 $4$ 情况的 $1$ 询问返回的值与 $p$ 相关,我们考虑从此处入手。

由于我们需要得知具体的 $p$ 中的每一个元素的值,考虑可以对两个元素同时进行 $1$ 情况的 $2$ 询问和 $4$ 情况的 $1$ 询问,以得到这两个元素中的较大值和较小值,但无法确定这两个值具体对应的位置。接着可以再通过 $2$ 情况和 $3$ 情况下的询问确定这两个元素的具体大小关系,就可以确定这两个位置上分别的值。

具体地,我们可以先考虑将 $n$ 长度的排列两两分组,如果 $n$ 为奇数则先忽略最后一个元素。对于每组内的两个元素:

  1. 询问 ? 2 i j 1,在大部分情况下 $p_i\ge1,~p_j\ge2$,可以对应 $1$ 情况,得到 $\min(p_i,p_j)$;当 $p_j=1$ 时该询问会对应 $2$ 情况,返回 $2$。我们可以对于所有返回值为 $2$ 的情况再询问 ? 1 i j 1,若返回值为 $2$ 则确认对应 $1$ 情况,$\min(p_i,p_j)=2$;否则返回值一定为 $1$,确认对应 $2$ 情况,$p_j=1$。
  2. 询问 ? 1 i j n-1,在大部分情况下 $p_i \le n-1,~p_j \le n$,可以对应 $4$ 情况,得到 $\max(p_i,p_j)$;当 $p_i=n$ 时该询问会对应 $2$ 情况,返回 $n-1$。我们可以对于所有返回值为 $n-1$ 的情况再询问 ? 2 i j n-1,若返回值为 $n-1$ 则确认对应 $4$ 情况,$\max(p_i,p_j)=n-1$;否则返回值一定为 $n$,确认对应 $2$ 情况,$p_i=n$。
  3. 询问 ? 1 i j min(p[i],p[j]),若返回值为 $\min(p_i,p_j)$ 则说明对应 $2$ 情况,$p_i > \min(p_i,p_j),~p_j<\min(p_i,p_j)+1$,所以 $p_i>p_j$;否则返回值一定为 $\min(p_i,p_j)+1$,对应 $3$ 情况,$p_i<\min(p_i,p_j),~p_j>\min(p_i,p_j)+1$,所以 $p_i < p_j$。(由于忽略了相等的情况所以式子可能不成立,但是足以判断两个元素的大小关系了)
  4. 对于上一步中得到的 $p_i$ 与 $p_j$ 的大小关系,和之前得到的 $\min(p_i,p_j),~\max(p_i,p_j)$,得到 $p_i,~p_j$ 的值。

对于 $n$ 为奇数的情况,在前 $n-1$ 个元素的值被求出后,找到那个没有被求出过的值赋值到 $p[n]$ 即可。

对于每两个元素我们进行了大约三次操作,且步骤 $1$ 和步骤 $2$ 中用于检验的询问次数相当少,所以总操作次数大约为 $\lfloor \frac {3 \times n} 2 \rfloor$,可以通过本题。

代码

如果上面的解释看懵了,也许可以尝试看一下代码。

代码比解释清楚多了

/**
 * @author Macesuted (macesuted@qq.com)
 * @copyright Copyright (c) 2021
 */

#include <bits/stdc++.h>
using namespace std;

int ask1(int i, int j, int p) {
    cout << "? 1 " << i << ' ' << j << ' ' << p << endl;
    int ret;
    cin >> ret;
    return ret;
}
int ask2(int i, int j, int p) {
    cout << "? 2 " << i << ' ' << j << ' ' << p << endl;
    int ret;
    cin >> ret;
    return ret;
}

int p[10005];
bool vis[10005];

int main() {
    ios::sync_with_stdio(false);
    int _;
    cin >> _;
    while (_--) {
        int n;
        cin >> n;
        for (register int i = 1; i <= n; i++) vis[i] = false;
        for (register int i = 1; i < n; i += 2) {
            int ret = ask1(i, i + 1, n - 1);
            p[i] = (ret == n - 1 && ask2(i, i + 1, n - 1) == n) ? n : ret;
            ret = ask2(i, i + 1, 1);
            p[i + 1] = (ret == 2 && ask1(i, i + 1, 1) == 1) ? 1 : ret;
            if (ask1(i, i + 1, p[i + 1]) == p[i + 1] + 1) swap(p[i], p[i + 1]);
            vis[p[i]] = vis[p[i + 1]] = true;
        }
        if (n & 1)
            for (register int i = 1; i <= n; i++)
                if (!vis[i]) p[n] = i;
        cout << '!';
        for (register int i = 1; i <= n; i++) cout << ' ' << p[i];
        cout << endl;
    }
    return 0;
}

我缓慢吐出一串啊吧啊吧并不再想说话