Pagini recente » Cod sursa (job #1108484) | Cod sursa (job #650869) | Cod sursa (job #2374528) | Cod sursa (job #26848) | Cod sursa (job #3348631)
#include <bits/stdc++.h>
#define NMAX 100002
using namespace std;
ifstream fin("xormax.in");
ofstream fout("xormax.out");
struct Trie{
const int BITS = 22;
Trie *children[2] = {nullptr};
int sz = 0;
int idx;
void add_child(int x)
{
children[x] = new Trie;
}
void insert(int val, int i, int depth = 0)
{
idx = i;
sz++;
if(BITS + 1 == depth) return;
int bit = 1<<(BITS - depth);
if(val & bit){
if(children[1] == nullptr) add_child(1);
(*children[1]).insert(val, i, depth+1);
}else{
if(children[0] == nullptr) add_child(0);
(*children[0]).insert(val, i, depth+1);
}
}
void max_xor(int val, int &i,int & ret, int depth = 0)
{
i = idx;
if(BITS + 1 == depth) return;
int bit = 1<<(BITS - depth);
if(val & bit){///bitu ii 1
if(children[0] != nullptr){
(*children[0]).max_xor(val, i, ret, depth + 1);
}else{
ret += bit;
(*children[1]).max_xor(val, i,ret, depth + 1);
}
}else{///bitu ii 0
if(children[1] != nullptr){
ret += bit;
(*children[1]).max_xor(val, i,ret, depth + 1);
}else{
(*children[0]).max_xor(val, i,ret, depth + 1);
}
}
return;
}
pair<int,int> max_xor(int val)
{
int ret = 0;
int idx = 0;
max_xor(val, idx, ret);
return {idx,ret};
}
};
Trie trie;
int N;
int a[NMAX];
int prefix_xor[NMAX];///puteam si sa il fac o singura variabila
int max_xor;
int le, ri;
int main()
{
fin >> N;
for(int i=1;i<=N;i++){
fin >> a[i];
prefix_xor[i] = a[i] ^ prefix_xor[i-1];
}
for(int i=1;i<=N;i++){
trie.insert(prefix_xor[i-1], i-1);
auto [idx, val] = trie.max_xor(prefix_xor[i]);
if(max_xor < (val ^ prefix_xor[i])){
max_xor = val ^ prefix_xor[i];
le = idx + 1;
ri = i;
}
}
fout << max_xor << " " << le << " " << ri;
}