Pagini recente » Cod sursa (job #1894014) | Cod sursa (job #1838068) | Cod sursa (job #155126) | Cod sursa (job #1294730) | Cod sursa (job #2704483)
#include <fstream>
#include <vector>
#include <iostream>
using namespace std;
struct Node{
Node* ch[2];
int index;
Node()
{
ch[0] = ch[1] = NULL;
index = -1;
}
};
vector<int> query(Node* root, int val)
{
vector<int> ans(2);
ans[0] = 0;
for(int i = 25;i >= 0 && root;--i)
{
int bit = 0;
if(val & (1 << i))
bit = 1;
if(root->ch[1 - bit])
{
ans[0] |= 1 << i;
root = root->ch[1 - bit];
}
else
root = root->ch[bit];
}
if(root)
ans[1] = root->index;
return ans;
}
void insert(Node* root, int val, int index)
{
for(int i = 25;i >= 0;--i)
{
int bit = 0;
if(val & (1 << i))
bit = 1;
if(root->ch[bit] == NULL)
root->ch[bit] = new Node();
root = root->ch[bit];
}
root->index = index;
}
vector<int> solve(vector<int>& v, Node* root)
{
int n = v.size(), xor_pref = 0;
vector<int> ans(3);
ans[0] = 0;
for(int i = 0;i < n;++i)
{
xor_pref ^= v[i];
vector<int> ret = query(root, xor_pref);
if(ret[0] > ans[0])
{
ans[0] = ret[0];
ans[1] = ret[1] + 1;
ans[2] = i;
}
if(xor_pref > ans[0])
{
ans[0] = xor_pref;
ans[1] = 0;
ans[2] = i;
}
insert(root, xor_pref, i);
}
return ans;
}
int main()
{
ifstream in("xormax.txt");
ofstream out("xormax.out");
int n;
in >> n;
vector<int> v(n);
for(int i = 0;i < n;++i)
in >> v[i];
Node* root = new Node();
vector<int> ans = solve(v, root);
out << ans[0] << " " << ans[1] + 1 << " " << ans[2] + 1 << "\n";
in.close();
out.close();
}