CF1364E X-OR

(Updated: )
oi
,

题目链接：CF1364E

有一个固定的长度为 $n$ 的排列 $P$，其值域为 $[0,n-1]$，你可以进行不超过 $4269$ 次询问，之后你需要输出这个排列 $P$​。

你可以按照 ? a b 的格式进行询问，之后你会得到 $P_a$ 与 $P_b$ 的按位或。

保证 $3\le n\le 2048$，$0\le P_i\le n-1$。

Tutorial

首先发现如果找到 $0$ 的位置，其他的全部问一遍就都出来了，因此转化为如何找 $0$。

不妨先随机两个位置 $x,y$，再枚举其他所有 $i$：

  • $P_x P_y > P_y P_i$：$P_x$ 必然非 $0$，因此用 $i$ 代替 $x$ 继续循环。
  • $P_xP_y = P_yP_i$：$P_y$ 必然非 $0$，因此用 $i$ 代替 $y$ 继续循环。
  • $P_xP_y <P_yP_i$：$P_i$ 必然非 $0$，因此不换。

那么最后肯定剩下 $x,y$，其中一个必为 $0$。

于是我们可以再随机一个数 $i$：

  • $P_x P_i > P_yP_i$：$P_x$ 必然非 $0$，因此 $P_y=0$。
  • $P_xP_i < P_yP_i$：$P_y$ 必然非 $0$，因此 $P_x=0$。
  • $P_xP_i = P_yP_i$：分辨不出来啥再重新随一个:(

简单分析一下询问次数：

首先第一部分找到两个中必有 $0$ 的一对数字，扫了一次所有的点，而其中第二种情况需要多询问一次新的 $P_xP_i$的值（为下次循环做准备），而产生第二种情况的充要条件是 $P_x \& P_y = P_x,P_i\& P_y = P_i$，其概率可以估计为 $\sum_{i=1}^n\frac 1{n^3} 2^{2\operatorname{popcount}(i)}\approx 0.0056843422353267669677734375$，可以看出这是非常小的。

因此这部分的询问次数大约为 $0.0056843422353267669677734375\times 2048+2048\approx 2059$。

其次第二部分随到第三种情况的概率：$\sum_{i=1}^n \frac 1{n^2}2^{\operatorname{popcount}(i)}\approx 0.04223537445068359375$。

不妨设其期望次数为 $f$，则有 $f=0.04223537445068359375\times (f+1) +(1-0.04223537445068359375)\times 1$

因此 $f=1.0441$。

所以总询问次数期望为：$2059+1+2048=4108$，远远小于 $4269$。

Solution

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
#include<bits/stdc++.h>
#define Tp template<typename Ty>
#define Ts template<typename Ty,typename... Ar>
#define W while
#define I inline
#define RI register int
#define LL long long
#define Cn const
#define CI Cn int&
#define gc getchar
#define D isdigit(c=gc())
#define pc(c) putchar((c))
#define min(x,y) ((x)<(y)?(x):(y))
#define max(x,y) ((x)>(y)?(x):(y))
using namespace std;
namespace Debug{
    Tp I void _debug(Cn char* f,Ty t){cerr<<f<<'='<<t<<endl;}
    Ts I void _debug(Cn char* f,Ty x,Ar... y){W(*f!=',') cerr<<*f++;cerr<<'='<<x<<",";_debug(f+1,y...);}
    Tp ostream& operator<<(ostream& os,Cn vector<Ty>& V){os<<"[";for(Cn auto& vv:V) os<<vv<<",";os<<"]";return os;}
    #define gdb(...) _debug(#__VA_ARGS__,__VA_ARGS__)
}using namespace Debug;
namespace FastIO{
    Tp I void read(Ty& x){char c;int f=1;x=0;W(!D) f=c^'-'?1:-1;W(x=(x<<3)+(x<<1)+(c&15),D);x*=f;}
    Ts I void read(Ty& x,Ar&... y){read(x),read(y...);}
    Tp I void write(Ty x){x<0&&(pc('-'),x=-x,0),x<10?(pc(x+'0'),0):(write(x/10),pc(x%10+'0'),0);}
    Tp I void writeln(Cn Ty& x){write(x),pc('\n');}
}using namespace FastIO;
Cn int N=2e5+10;
int n,Ans[N];
I int Q(CI x,CI y){
    RI t;cout<<"? "<<x<<" "<<y<<endl;
    cin>>t;return t;
}
int main(){
    mt19937 mt(time(nullptr));
    RI i,x,y,v,t,q1,q2,p0;read(n);x=mt()%n+1,y=mt()%n+1;W(x==y) y=mt()%n+1;
    for(v=Q(x,y),i=1;i<=n;i++) if(i^x&&i^y){
        if(v>(t=Q(y,i))) x=i,v=t;
        else if(v==t) y=i,v=Q(x,y);
    }do{
    t=mt()%n+1;W(t==xt==y) t=mt()%n+1;
    if((q1=Q(x,t))>(q2=Q(y,t))) p0=y;else if(q1<q2) p0=x;}while(!p0);
    for(i=1;i<=n;i++) Ans[i]=i==p0?0:Q(p0,i);
    for(cout<<"! ",i=1;i<=n;i++) cout<<Ans[i]<<" ";cout<<endl;
    return 0;
}