Pagini recente » Cod sursa (job #1208833) | Cod sursa (job #3154201) | Cod sursa (job #913746) | Cod sursa (job #557976) | Cod sursa (job #997635)
Cod sursa(job #997635)
#include <iostream>
#include <fstream>
#include <cstring>
#include <climits>
using namespace std;
const int Nmax = 100005;
struct Trie
{
int indice;
Trie *son[2];
Trie()
{
son[0] = 0;
son[1] = 0;
indice = 0;
}
};
Trie *T = new Trie;
int N;
int X[Nmax];
string sir;
int maxim = -INT_MAX, stanga, dreapta;
void read()
{
ifstream f("xormax.in");
f >> N;
getline( f, sir );
getline( f, sir );
unsigned l = sir.size();
int index = 0, nr = 0;
for ( unsigned i = 0; i <= l; ++i )
if ( isdigit( sir[i] ) )
nr = nr * 10 + ( sir[i] - 48 );
else
{
X[ ++index ] = nr ^ X[index - 1];
nr = 0;
}
f.close();
}
void insereaza( Trie *nod, int sum, int exp, int index )
{
if ( exp == -1 )
{
nod->indice = index;
return;
}
bool bit = ( sum & ( 1 << exp ) );
if ( nod->son[bit] == 0 )
nod->son[bit] = new Trie;
insereaza( nod->son[bit], sum, exp - 1, index );
}
void query( int sum, int finish )
{
Trie *nod = T;
for ( int i = 21; i >= 0; i-- )
{
bool bit = sum & ( 1 << i );
if ( nod->son[bit ^ 1] )
nod = nod->son[bit ^ 1];
else
nod = nod->son[bit];
}
if ( sum ^ X[nod->indice] > maxim )
{
maxim = sum ^ X[nod->indice];
stanga = nod->indice + 1;
dreapta = finish;
}
}
void solve()
{
insereaza( T, 0, 21, 0 );
for ( int i = 1; i <= N; ++i )
{
insereaza( T, X[i], 21, i );
}
for ( int i = 1; i <= N; ++i )
{
query( X[i], i );
}
}
void print()
{
ofstream g("xormax.out");
g << maxim << " " << stanga << " " << dreapta << "\n";
g.close();
}
int main()
{
read();
solve();
print();
return 0;
}