Perfect Security

题目大意

你有两串长度为 的序列,让你对第二串数排列一下,使得这两串数对应的数的异或序列字典序最小(一个数作为一个关键字,而不是一个数的每一位都是关键字)

分析

考虑贪心,让 和最优的 匹配,然后删掉与 匹配的 ,然后去匹配 ,直到
正确性显然,就不用再证明了
然后就是如何找到与 相匹配的 ,并删除它?
考虑将所有的 插入到 字典树中,然后每次插入对路径整体 ,查询的时候就是尽可能的从高位开始找到二进制下最相近的状态,然后对查询路径整体 ,就完成了上述操作

Code

#include <cstdio>

const int maxn = 3e5 + 10;
int son[maxn * 30][2], siz[maxn * 30][2];
int n, id, temp, a[maxn];

inline int __read()
{
    int x(0), t(1);
    char o (getchar());
    while (o < '0' || o > '9') {
        if (o == '-') t = -1;
        o = getchar();
    }
    for (; o >= '0' && o <= '9'; o = getchar()) {
        x = (x << 1) + (x << 3) + (o ^ 48);
    }
    return x * t;
}

inline void insert(int x)
{
    int p(0);
    for (int i = 30; ~i; --i) {
        int sta = x >> i & 1;
        if (!son[p][sta]) son[p][sta] = ++id;
        siz[p][sta]++;
        p = son[p][sta];
    }
}

inline int query(int x)
{
    int p(0), res(0);
    for (int i = 30; ~i; --i) {
        int sta = x >> i & 1;
        if (!siz[p][sta]) sta ^= 1;
        siz[p][sta]--;
        p = son[p][sta];
        res = (res << 1) | sta;
    }
    return res ^ x;
}

int main()
{
    n = __read();
    for (int i = 1; i <= n; ++i) a[i] = __read();
    for (int i = 1; i <= n; ++i) {
        temp = __read();
        insert(temp);
    }
    for (int i = 1; i <= n; ++i) printf ("%d ", query(a[i]));
}