Pagini recente » Cod sursa (job #3231666) | Cod sursa (job #121481) | Cod sursa (job #1409090) | Cod sursa (job #2933517) | Cod sursa (job #1001235)
/*
PROB: infoarena
LANG: C++
*/
#include <fstream>
//#define DEBUG
#ifndef DEBUG
#define PRINT(x)
#define D if(0)
#else
#include <iostream>
#define PRINT(x) \
cout<<#x<<":\t"<<x<<endl
#define D if(1)
#endif
using namespace std;
const char InFile[]="xormax.in";
const char OutFile[]="xormax.out";
const int MaxN=21;
ifstream fin(InFile);
ofstream fout(OutFile);
struct TrieNode
{
TrieNode()
{
child[0]=child[1]=NULL;
start=0;
}
int start;
TrieNode *child[2];
};
int N,A,CurrXOR,CurrIndex,Sol,SolEnd,SolStart,Array[MaxN],BestXOR,BestStart;
TrieNode root;
inline void MakeArray(int A)
{
for(register int i=20;i>=0;--i)
{
Array[i]=A&1;
A>>=1;
}
}
inline int NOT(const int &A)
{
if(A==0)
{
return 1;
}
return 0;
}
void TrieSearch(TrieNode *node, int index=0)
{
if(index==21)
{
BestStart=node->start;
return;
}
if(node->child[NOT(Array[index])])
{
BestXOR<<=1;
BestXOR+=NOT(Array[index]);
TrieSearch(node->child[NOT(Array[index])],index+1);
}
else
{
BestXOR<<=1;
BestXOR+=Array[index];
TrieSearch(node->child[Array[index]],index+1);
}
}
void TrieAdd(TrieNode *node, int index=0)
{
if(index==21)
{
node->start=CurrIndex;
return;
}
if(!node->child[Array[index]])
{
node->child[Array[index]]=new TrieNode;
}
TrieAdd(node->child[Array[index]],index+1);
}
int main()
{
fin>>N;
CurrIndex=0;
MakeArray(0);
TrieAdd(&root);
for(register int i=1;i<=N;++i)
{
CurrIndex=i;
fin>>A;
CurrXOR^=A;
MakeArray(CurrXOR);
BestXOR=0;
TrieSearch(&root);
PRINT(CurrXOR<<" "<<BestXOR);
PRINT(Sol<<" "<<(CurrXOR^BestXOR));
if((CurrXOR^BestXOR)>Sol)
{
PRINT("UPDATE");
Sol=CurrXOR^BestXOR;
SolStart=BestStart+1;
SolEnd=i;
}
TrieAdd(&root);
}
fin.close();
fout<<Sol<<" "<<SolStart<<" "<<SolEnd;
fout.close();
return 0;
}