Ta dựng đồ thị vô hướng ~G = (V,E):~

• ~V = \{1,2,...,2^{19}-1\}~

• ~E~ là tập bao gồm các cạnh:

  • ~v \oplus 2^0~

  • ~v \oplus 2^1~

  • ...

  • ~v \oplus 2^{18}~

Từ đây, bài toán trở thành, cho ~k~ đỉnh đặc biệt trong đồ thị, với mỗi đỉnh trong ~k~ đỉnh đó, tìm đỉnh đặc biệt gần nó nhất.

Để giải quyết bài toán này, ta có thể xét mọi bit ~i~ từ ~0~ tới ~18~, phân đồ thị ra làm hai tập:

• Tập ~A~ gồm các đỉnh có bit ~i~ được bật.

• Tập ~B~ gồm các đỉnh có bit ~i~ được tắt.

Từ đây, ta có thể ~BFS~ từ tập ~A~ sang tập ~B~ (sử dụng BFS đa nguồn), tương tự với ~BFS~ từ tập ~B~ sang tập ~A~ và cập nhật. Sau khi xét hết đủ các bit, ta sẽ thu được đáp án.

Lưu ý trường hợp một số xuất hiện nhiều lần, lúc đó đáp án của nó sẽ bằng ~0~.

#include <bits/stdc++.h>

using namespace std;
using ll = long long;
using ld = long double;
using ull = unsigned long long;

constexpr bool typetest = 0;
constexpr int N = 5e5 + 5;
constexpr int Inf = 1e9 + 7;
int n;
int a[N], cnt[N];
int ans[N], d[N];

void Read()
{
    cin >> n;
    for (int i = 1; i <= n; ++i) {
        cin >> a[i];
        ++cnt[a[i]];
    }
}

#define bit(i, x) (((x) >> (i)) & 1)

void BFS(int bitPos, int bitVal) {
    queue<int> q;
    for (int i = 0; i < N; ++i) {
        d[i] = Inf;
        if (bit(bitPos, i) == bitVal && cnt[i] > 0) {
            q.push(i);
            d[i] = 0;
        }
    }

    while (!q.empty()) {
        int c = q.front();
        q.pop();

        for (int i = 0; i < 19; ++i) {
            int v = c ^ (1 << i);
            if (v < N && d[v] == Inf) {
                d[v] = d[c] + 1;
                q.push(v);
            }
        }
    }

    for (int i = 0; i < N; ++i) {
        if (bit(bitPos, i) != bitVal && cnt[i] > 0) {
            ans[i] = min(ans[i], d[i]);
        }
    }
}

void Solve()
{
    for (int i = 0; i < N; ++i) {
        ans[i] = Inf;
    }

    for (int i = 0; i < 19; ++i) {
        BFS(i, 0);
        BFS(i, 1);
    }

    for (int i = 1; i <= n; ++i) {
        cout << (cnt[a[i]] > 1 ? 0 : ans[a[i]]) << " ";
    }
}

int32_t main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    if (fopen("tests.inp", "r"))
    {
        freopen("test.inp", "r", stdin);
        freopen("test.out", "w", stdout);
    }

    int t(1);
    if (typetest)
        cin >> t;

    for (int _ = 1; _ <= t; ++_)
    {
        // cout << "Case #" << _ << endl;
        Read();
        int startTime = 1000 * clock() / CLOCKS_PER_SEC;
        Solve();
        int endTime = 1000 * clock() / CLOCKS_PER_SEC;
        cerr << "\nTime elapsed: " << endTime - startTime << "ms\n";
    }
}