Pagini recente » Cod sursa (job #1865892) | Cod sursa (job #2425054) | Cod sursa (job #2619465) | Cod sursa (job #1022653) | Cod sursa (job #3154270)
#include <bits/stdc++.h>
#define SIGMA 3
using namespace std;
/// INPUT / OUTPUT
const string problem = "xormax";
ifstream fin(problem + ".in");
ofstream fout(problem + ".out");
/// DATA STRUCTURES
struct ans_type
{
int st, maxi;
};
struct Trie
{
struct Node
{
int rasp, poz;
Node *sons[SIGMA];
};
Node *root = new Node();
/// ADD A NUMBER IN ITS BINARY REPRESENTATION BY MOST SIGNIFICANT BIT
inline void add(int x, int cnt, int position, Node *curr)
{
if(cnt == -1)
{
//if(!curr->rasp)
//{
curr->poz = position;
//}
curr->rasp++;
return;
}
int last_bit = ((x >> cnt) & 1);
if(curr->sons[last_bit] == NULL)
curr->sons[last_bit] = new Node();
add(x, cnt - 1, position, curr->sons[last_bit]);
}
/// GETTING THE MAXIMUM XOR PER INTERVAL
inline ans_type query(int x, int cnt, int ans, Node *curr)
{
if(cnt == -1)
{
return {curr->poz, ans};
}
int last_bit = ((x >> cnt) & 1);
if(curr->sons[!last_bit])
{
ans += (1 << cnt);
return query(x, cnt - 1, ans, curr->sons[!last_bit]);
}
else
return query(x, cnt - 1, ans, curr->sons[last_bit]);
}
};
/// GLOBAL VARIABLES
const int NMAX = 1e5 + 5;
int n, ans = 0, st = 0 , dr = 1;
int arr[NMAX], xors[NMAX];
Trie xor_max;
int main()
{
/// IMPROVED INPUT / OUTPUT
ios::sync_with_stdio(false);
fin.tie(NULL);
fout.tie(NULL);
cin >> n;
for(int i = 1; i <= n; ++ i)
{
cin >> arr[i];
}
xor_max.add(0, 22, 0, xor_max.root);
xors[1] = arr[1];
xor_max.add(xors[1], 22, 1, xor_max.root);
for(int i = 2; i <= n; ++ i)
{
xors[i] = xors[i - 1] ^ arr[i];
xor_max.add(xors[i], 22, i, xor_max.root);
ans_type pos_ans = xor_max.query(xors[i], 22, 0, xor_max.root);
if(pos_ans.maxi > ans)
{
ans = pos_ans.maxi;
st = pos_ans.st;
dr = i;
}
}
cout << ans << ' ' << st + 1 << ' ' << dr << '\n';
return 0;
}