Pagini recente » Cod sursa (job #908513) | Cod sursa (job #1942150) | Cod sursa (job #914654) | Cod sursa (job #1100718) | Cod sursa (job #997643)
Cod sursa(job #997643)
#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 = -1, stanga, dreapta;
void read()
{
ifstream f("xormax.in");
f >> N;
for ( int i = 1; i <= N; ++i )
{
f >> X[i];
X[i] ^= X[i - 1];
}
/*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) {
int i;
Trie *nod = T;
for( i = 21 ; i >= 0 ; --i ) {
bool t = (sum & (1 << i));
if ( nod -> son[t ^ 1] )
nod = nod -> son[t ^ 1];
else
nod = nod -> son[t];
}
if ( (sum xor X[nod->indice]) > maxim ) {
maxim = sum xor 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;
}