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
47
48
49
50
51
52
53
54
55
56
| #include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>
#include <cctype>
#define maxn 200010
#define ll long long
#define cn const node
#define gc getchar
#define pb push_back
#define offset 200000
using namespace std;
ll read() {
ll x = 0, f = 0; char c = gc();
while (!isdigit(c)) f |= c == '-', c = gc();
while (isdigit(c)) x = x * 10 + c - '0', c = gc();
return f ? -x : x;
}
inline int max(int a, int b, int c) { return max(a, max(b, c)); }
int n, m, a[maxn];
#define ch x >> i & 1
#define lc T[i].nxt[0]
#define rc T[i].nxt[1]
struct Trie {
int nxt[2], sz;
} T[maxn * 31]; int rt = 1, top = 1;
void insert(int x) {
int now = rt;
for (int i = 31; ~i; --i) {
if (!T[now].nxt[ch]) T[now].nxt[ch] = ++top;
now = T[now].nxt[ch];
} T[now].sz = 1;
}
int ans;
int dfs(int i, int d) {
if (!i) return 0; int ls, rs;
if (d == -1) return min(2, T[i].sz);
ls = dfs(lc, d - 1); T[i].sz += T[lc].sz;
rs = dfs(rc, d - 1); T[i].sz += T[rc].sz;
if (ls == 2 && rs == 2) ans += min(T[lc].sz, T[rc].sz) - 1, T[i].sz -= min(T[lc].sz, T[rc].sz) - 1;
return min(2, ls + rs);
}
int main() {
cin >> n;
for (int i = 1; i <= n; ++i) a[i] = read(), insert(a[i]);
dfs(rt, 31); cout << ans << endl;
return 0;
}
|