Pagini recente » Statistici costiniulia (costiniulia) | Borderou de evaluare (job #1062418) | Borderou de evaluare (job #2631509) | Cod sursa (job #2012220) | Cod sursa (job #2307635)
#include <fstream>
using namespace std;
ifstream fin("xormax.in");
ofstream fout("xormax.out");
class Node{
public:
Node *fii[2];
Node()
{
fii[0] = NULL;
fii[1] = NULL;
}
};
int N, xors[100005];
int bestXor, stBestXor, drBestXor;
bool stSet = false;
Node* InsertTrie(Node* node, int val, int pas)
{
if(node == NULL)
node = new Node;
if(pas != 20)
node = InsertTrie(node-> fii[val & 1], val >> 1, pas + 1);
return node;
}
int SearchBestXor(Node* node, int val, int pas)
{
if(pas == 20)
return 0;
if(node-> fii[!(val & 1)])
return (1 << pas) + SearchBestXor(node-> fii[!(val & 1)], val >> 1, pas + 1);
else
return SearchBestXor(node-> fii[val & 1], val >> 1, pas + 1);
}
int main()
{
int x;
Node* trie = NULL;
fin >> N;
fin >> xors[1];
for(int i = 2; i <= N; i++)
{
fin >> x;
xors[i] = xors[i - 1] ^ x;
}
for(int i = 1; i <= N; i++)
{
if(i == 1 && xors[i] > bestXor)
{
bestXor = xors[i];
stBestXor = drBestXor = i;
stSet = true;
}
if(i > 1 && (xors[i - 1] ^ xors[i]) > bestXor)
{
bestXor = xors[i - 1] ^ xors[i];
stBestXor = drBestXor = i;
stSet = true;
}
trie = InsertTrie(trie, xors[i], 0);
int currentBestXor = SearchBestXor(trie, xors[i], 0);
if(currentBestXor > bestXor)
{
bestXor = currentBestXor;
drBestXor = i;
stSet = false;
}
}
if(!stSet)
{
for(int i = drBestXor - 1; i >= 1; i--)
if((xors[i] ^ xors[drBestXor]) == bestXor)
{
stBestXor = i;
break;
}
}
fout << bestXor << ' ' << stBestXor << ' ' << drBestXor << '\n';
return 0;
}