CF1583D

DDF_ · 2025-09-10 19:47:26 · 题解

题解

先求出 p_{n} 的值。

具体地，先从 1 到 n-1 枚举一个数 x，询问 a=[1,1,1,\cdots,1,x+1]，此时若返回 0，则 p_{n} 已经确定，即 p_{n}=n+1-x；若返回其他的 k，则标记 p_{k}=p_{n}+x，求出 p_{n} 后再将所有被标记的 p_{k} 处理为正确的值。

特殊地，若 \forall x \in [1,n-1]，返回的 k 均不为 0，则 p_{n}=1，然后此时所有 p_{i} 已经被标记，于是就可以在 n-1 步内求出序列。

:::info[为什么这样求] 根据排列性质，如果 p_{n}+x \le n，则这个值必定在排列中出现过，且整个排列没有重复的元素。因此可以直接询问 a=[0,0,0,\cdots,0,x]。

但是因为询问的数组必须满足所有元素在 [1,n]，所以将整个数组往上 +1 后询问。 :::

这样处理之后，发现所有大于 p_{n} 的位置都会被标记，所以只需要求小于 p_{n} 的位置了。

类似地，对于一个数 x 的位置（x<p_{n}），可以询问数组 a=[p_{n}-x+1,p_{n}-x+1，\cdots,1]，返回值 k 即为 x 的位置。

:::info[为什么这样构造] 可以发现构造的数组 a 满足除下标 n 外的所有值都和 a_{n} 相差 p_{n}-x。所以这个数组其实等价于 a=[0,0,0,\cdots,0,x-p_{n}]。 :::

这样，就可以在 n 步或者 n-1 步内求出 p。

代码

#include<bits/stdc++.h>
using namespace std;
int n;
int p[105];
int main() {
    scanf("%d",&n);
    int pd=1;
    p[n]=n+1;
    while(pd) {
        p[n]--;
        if(p[n]==1) break;
        printf("? ");
        for(int i=1;i<n;i++) printf("1 ");
        printf("%d\n",n-p[n]+2);
        fflush(stdout);
        scanf("%d",&pd);
        p[pd]=n-p[n]+1;
    }
    for(int i=1;i<n;i++) if(p[i]) p[i]+=p[n];
    pd=0;
    for(int i=1;i<p[n];i++) {
        printf("? ");
        for(int j=1;j<n;j++) printf("%d ",p[n]-i+1);
        puts("1");
        fflush(stdout);
        scanf("%d",&pd);
        p[pd]=i;
    }
    printf("! ");
    for(int i=1;i<=n;i++) printf("%d ",p[i]);
    return 0;
}