题目描述

大概意思就是给你一个长度为$n(n<=2^{11})$的从[0,n-1]排列数,然后你可以问他4269下，i,j(i!=j)
p[i] | p[j]的结果，问你最后序列是什么

解题思路

1. 我们先把每一位(共11位)是0的坐标先处理出来
2. 我们通过已经是0的坐标我们就可以通过挨个查询就可以知道每个数的具体数值
3. 我们用方案2，采用逐步收缩范围的方式，如果a|b == a,那么我们说b的二进制至少比a少1，所以我们每次至少收缩一位
4. 我们利用方案3，我们可以快速找到0的坐标，然后用0把每一位的答案填出来，本题结束

正确性证明

1. 显然方案4需要2048次询问，方案3我们每次收缩，需要2048 + 11 * 11次询问就够了,所以我们只能留给方案1，52次询问。
2. 一位一位问是不行的，因为最倒霉的情况，每一位都要问n/2下，所以是不行的。我们考虑随机来问，对于每一位都会有n/2个,一共11位，彼此都是相互独立的,对于每一位我们要问出0才行。对于1位成功的概率，$1 - (3/4) ^ {52}$,11位同时成功的概率是，$(1 - (3/4) ^ {52}) ^ {11}$ ,用python计算得 0.9999964958903321 这个成功率我们近似看成1，一定会成功。 证毕
   这个成功率，如果你WA了建议去买彩票

代码

#include <bits/stdc++.h>

using namespace std;

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

const int N = 2510;

int ans[N],n;

int B[11];

int ask(int a,int b)
{
    cout << "?";
    cout << " " << a << " " << b << endl;
    cout.flush();

    int x;

    cin >> x;

    return x;
}

void reply()
{
    cout << "!";
    for(int i=1;i<=n;i++)
        cout << " " << ans[i];
    cout << endl;
    cout.flush();
}

bool check()
{
    for(int i=0;i<11;i++)
        if(B[i] == -1)
            return false;
    return true;
}

int get(int x)
{
    int res = 0;

    for(int i=0;i<11;i++)
    {
        if(x == B[i]) continue;

        if(ask(x,B[i]) >> i & 1)
            res += 1 << i; 
    }

    return res;
}

int main(){

    ios :: sync_with_stdio(false);
    cin.tie(0);

    cin >> n;

    memset(B,-1,sizeof B);

    while(!check())
    {
        int a = uniform_int_distribution<int>(1,n)(rng);
        int b = uniform_int_distribution<int>(1,n)(rng);

        if(a == b) continue;

        int x = ask(a,b);

        for(int i=0;i<11;i++)
        {
            if((x >> i & 1) == 0)
                B[i] = a;
        }
    }   

    int idx = 1;
    int val = get(idx);

    for(int i=2;i<=n;i++)
    {
        if(ask(i,idx) == val)
        {
            idx = i;
            val = get(idx);
        }
    }

    for(int i=1;i<=n;i++)
    {
        if(i != idx)
            ans[i] = ask(i,idx);
    }

    reply();


    return 0;
}