forked from usamajay/hacktoberfest2021-1
-
Notifications
You must be signed in to change notification settings - Fork 0
/
Max_xor using Trie
103 lines (95 loc) · 3.2 KB
/
Max_xor using Trie
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
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
/*
░░░░░░░░░▄░░░░░░░░░░░░░░▄░░░░
░░░░░░░░▌▒█░░░░░░░░░░░▄▀▒▌░░░
░░░░░░░░▌▒▒█░░░░░░░░▄▀▒▒▒▐░░░
░░░░░░░▐▄▀▒▒▀▀▀▀▄▄▄▀▒▒▒▒▒▐░░░
░░░░░▄▄▀▒░▒▒▒▒▒▒▒▒▒█▒▒▄█▒▐░░░
░░░▄▀▒▒▒░░░▒▒▒░░░▒▒▒▀██▀▒▌░░░
░░▐▒▒▒▄▄▒▒▒▒░░░▒▒▒▒▒▒▒▀▄▒▒▌░░
░░▌░░▌█▀▒▒▒▒▒▄▀█▄▒▒▒▒▒▒▒█▒▐░░
░▐░░░▒▒▒▒▒▒▒▒▌██▀▒▒░░░▒▒▒▀▄▌░
░▌░▒▄██▄▒▒▒▒▒▒▒▒▒░░░░░░▒▒▒▒▌░
▀▒▀▐▄█▄█▌▄░▀▒▒░░░░░░░░░░▒▒▒▐░
▐▒▒▐▀▐▀▒░▄▄▒▄▒▒▒▒▒▒░▒░▒░▒▒▒▒▌
▐▒▒▒▀▀▄▄▒▒▒▄▒▒▒▒▒▒▒▒░▒░▒░▒▒▐░
░▌▒▒▒▒▒▒▀▀▀▒▒▒▒▒▒░▒░▒░▒░▒▒▒▌░
░▐▒▒▒▒▒▒▒▒▒▒▒▒▒▒░▒░▒░▒▒▄▒▒▐░░
░░▀▄▒▒▒▒▒▒▒▒▒▒▒░▒░▒░▒▄▒▒▒▒▌░░
░░░░▀▄▒▒▒▒▒▒▒▒▒▒▄▄▄▀▒▒▒▒▄▀░░░
░░░░░░▀▄▄▄▄▄▄▀▀▀▒▒▒▒▒▄▄▀░░░░░
░░░░░░░░░▒▒▒▒▒▒▒▒▒▒▀▀░░░░░░░░
*/
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define lli long long int
#define vi vector<int>
#define vvi vector<vi>
#define vll vector<long long>
#define vb vector<bool>
#define pb push_back
#define pii pair<int,int>
#define all(x) x.begin(),x.end()
struct Node{
Node *links[2];
bool containskey(int bit){
return (links[bit]!=NULL);
}
Node *get(int bit){
return links[bit];
}
void put(int bit,Node* node){
links[bit]=node;
}
};
class Trie{
public:
Node* root;
Trie(){
root=new Node();
}
public:
void insert(int num){
Node* node=root;
for(int i=31;i>=0;i--){
int bit=(num>>i) & 1;
if(!node->containskey(bit)){
node->put(bit,new Node());
}
node=node->get(bit);
}
}
public:
int getmax(int num){
Node* node=root;
int maxn=0;
for(int i=31;i>=0;i--){
int bit=(num>>i) & 1;
if(node->containskey(1-bit)){
maxn=maxn | (1<<i);
node=node->get(1-bit);
}
else{
node=node->get(bit);
}
}
return maxn;
}
};
int maxor(vi &v1,vi &v2,int n,int m){
Trie trie;
for(auto &it: v1){
trie.insert(it);
}
int maxi=0;
for(auto &it: v2){
maxi=max(maxi,trie.getmax(it));
}
return maxi;
}
int main(){
ios_base::sync_with_stdio(false);
cin.tie(NULL);
return 0;
// mere code m ho jaoge gum...de***** c****** ho tum A_F
}