Pagini recente » Cod sursa (job #1270028) | Cod sursa (job #1809193) | Cod sursa (job #2091665) | Diferente pentru problema/sever intre reviziile 18 si 17 | Cod sursa (job #3354250)
#include <bits/stdc++.h>
using namespace std;
struct TrieNode{
string val;
TrieNode *parent = nullptr;
unordered_map<string, TrieNode*> children;
TrieNode() = default;
TrieNode(string val) : val(val) {}
};
class Trie{
TrieNode *root = new TrieNode(" ");
public:
void insert(vector<string> s, int index){
int i = 0;
TrieNode *comp = root;
while(i < s.size() && comp->children.find(s[i]) != comp->children.end()){
comp = comp->children[s[i]];
i++;
}
while(i < s.size()){
comp->children[s[i]] = new TrieNode(s[i]);
comp->children[s[i]]->parent = comp;
comp = comp->children[s[i]];
i++;
}
comp->children["#" + to_string(index)] = nullptr;
}
string find(vector<string> bin){
int i = 0;
TrieNode *comp = root;
while(i < 21){
string opposite = to_string(!stoi(bin[i]));
string same = to_string(stoi(bin[i]));
if(comp->children.find(opposite) != comp->children.end()){
comp = comp->children[opposite];
}
else if(comp->children.find(same) != comp->children.end()){
comp = comp->children[same];
}
i++;
}
for(const auto &x : comp->children){
return x.first;
}
return "-1";
}
};
int main(){
ifstream fin("xormax.in");
ofstream fout("xormax.out");
int n;
unsigned long long val;
fin>>n;
vector<unsigned long long> prefix_xor(n+1);
vector<string> bin(21, "0");
Trie trie;
prefix_xor[0] = 0;
unsigned long long temp_max = 0, ind_max, ind_min, max = 0;
for(int i = 1; i <= n; i++){
fin>>val;
prefix_xor[i] = prefix_xor[i-1] ^ val;
val = prefix_xor[i];
int j = 20;
temp_max = 0;
while(val && j >= 0){
bin[j] = '0' + val%2;
val /= 2;
j--;
}
trie.insert(bin, i);
string ind = trie.find(bin);
ind[0] = ' ';
j = stoi(ind);
temp_max = prefix_xor[i] ^ prefix_xor[j];
if(temp_max > max){
max = temp_max;
ind_max = i, ind_min = j+1;
}
bin.assign(21, "0");
}
fout<<max<<" "<<ind_min<<" "<<ind_max;
return 0;
}