Pagini recente » Istoria paginii runda/concurs_2014/clasament | Cod sursa (job #1526568) | Cod sursa (job #943849) | Cod sursa (job #1008300) | Cod sursa (job #2307777)
#include <fstream>
using namespace std;
ifstream fin("xormax.in");
ofstream fout("xormax.out");
int N, xors[100005];
int xormax, st, dr;
class Node{
public:
Node* fii[2];
Node()
{
fii[0] = NULL;
fii[1] = NULL;
}
};
Node* InsertTrie(Node* node, int val, int e)
{
if(node == NULL)
node = new Node;
if(e > 0)
node-> fii[val & (1 << e)] = InsertTrie(node-> fii[val & (1 << e)], val, e - 1);
return node;
}
int SearchXorMax(Node* node, int val, int e)
{
if(e == -1)
return 0;
if(node-> fii[!(val & (1 << e))])
return (1 << e) + SearchXorMax(node-> fii[!(val & (1 << e))], val, e - 1);
return SearchXorMax(node-> fii[val & (1 << e)], val, e - 1);
}
int main()
{
fin >> N;
Node* trie = NULL;
trie = InsertTrie(trie, 0, 20);
for(int i = 1; i <= N; i++)
{
fin >> xors[i];
xors[i] ^= xors[i - 1];
int currentXorMax = SearchXorMax(trie, xors[i], 20);
if(currentXorMax > xormax)
{
xormax = currentXorMax;
dr = i;
}
trie = InsertTrie(trie, xors[i], 20);
}
for(int i = dr - 1; i >= 1; i--)
if((xors[i] ^ xors[dr]) == xormax)
{
st = i + 1;
break;
}
fout << xormax << ' ' << st << ' ' << dr;
return 0;
}