Pagini recente » Cod sursa (job #183785) | Cod sursa (job #2684772) | Cod sursa (job #3351734) | Cod sursa (job #119592) | Cod sursa (job #3348634)
#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, nullptr};
int sz = 0;
int idx;
void add_child(int x)
{
children[x] = new Trie;
}
void insert(int val, int i, int depth = 0)
{
sz++;
if(BITS + 1 == depth){
idx = i;
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)
{
if(BITS + 1 == depth){
i = idx;
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;
}