「CF1521C」Nastia and a Hidden Permutation

发表于 分类于

$Link$

本题是一道交互题。

有一个长度为 $n$ 的排列，你有两种询问：

  • $\max(\min(x,p_i),\min(x+1,p_j))$。
  • $\min(\max(x,p_i),\max(x+1,p_j)$。

其中 $x,i,j$ 由你决定，需要满足 $i\not=j,1\le x\le n-1$。

你可以做出最多 $\lfloor\frac{3n}{2}\rfloor+30$ 次询问，并确定这个排列每个位置上的数。

共有 $t$ 组数据。

$1\le t\le10^4,3\le n\le 10^4,\sum n\le2\times10^4$。

一道蛮有意思的交互。

根据套路，我们先尝试找出 $1$，然后再推出整个排列。

考虑把询问中的一些东西定下来，只剩下我们想知道的东西。

我们使用操作 $2$，并令 $x=1$，这样第一个 $\max$ 就一定等于 $p_i$，第二个 $\max$ 就等于 $\max(2,p_j)$。

显然第二个 $\max\ge2$，于是返回值为 $1$ 当且仅当 $p_i=1$。

那我们随便固定一个 $j$，枚举 $i$，用 $n-1$ 次询问即可找出 $p_i=1$ 的位置。

那剩下的部分就很简单了，直接枚举 $j$，查询 $\max(\min(1,1),\min(2,p_j))$，返回值一定是 $p_j$，这里又用了 $n-1$ 次询问。

观察到限制是 $\frac{3n}{2}=n+\frac{n}{2}$，显然后半部分的操作无法省略，于是我们要把前半部分的询问次数减半。

注意到前半部分的询问中，$j$ 这个位置我们没有用到，再结合减半的目标，容易想到把整个序列两两分组询问。

我们再看一次询问 $\min(\max(1,p_i),\max(2,p_j))$ 能得出的结果：

  • 结果为 $1$，则 $p_i=1$。
  • 结果 $>2$，那 $p_i,p_j\not=1$。
  • 结果为 $2$，可以得到 $p_i\not=1,p_j=1/2$。

最坏情况下每次排除两个数，并且遇到了第三种情况且 $p_j=1/2$，分别再多消耗一次询问确定 $p_j$ 是否为 $1$，此时的询问次数为 $\lfloor\frac{n}{2}\rfloor+2$，即可通过本题。

$code$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
#include <iostream>
#include <cstdlib>
#include <cstdio>
using namespace std;
const int N = 1e4;

int tt;
int n, one;
int p[N + 1];

int main()
{
    scanf("%d", &tt);

    while (tt--) {
        one = 0;
        scanf("%d", &n);
        for (int i = 1; i < n; i += 2) {
            printf("? 2 %d %d 1\n", i, i + 1);
            fflush(stdout);
            int x;
            scanf("%d", &x);
            if (x == 1) {
                one = i;
                break;
            }
            if (x == 2) {
                printf("? 2 %d 1 1\n", i + 1);
                fflush(stdout);
                scanf("%d", &x);
                if (x == 1) {
                    one = i + 1;
                    break;
                }
            }
        }
        if (!one)
            one = n;
        for (int i = 1; i <= n; i++) {
            if (i == one) {
                p[i] = 1;
                continue;
            }
            printf("? 1 %d %d %d\n", one, i, n - 1);
            fflush(stdout);
            scanf("%d", &p[i]);
        }
        printf("!");
        for (int i = 1; i <= n; i++)
            printf(" %d", p[i]);
        printf("\n");
        fflush(stdout);
    }

    return 0;
}