Pagini recente » Cod sursa (job #1865191) | Cod sursa (job #522308) | tema | Cod sursa (job #1604674) | Cod sursa (job #997644)
Cod sursa(job #997644)
#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 insereaza( Trie *nod , int sum , int ind, int index) {
if (ind == -1) {
nod -> indice = index;
return;
}
bool t = ( sum & (1 << ind));
if ( nod -> son[t] == 0 )
nod -> son[t] = new Trie;
insereaza (nod -> son[t] , sum , ind - 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 )
{
query( X[i], i );
insereaza( T, X[i], 21, i );
}
for ( int i = 1; i <= N; ++i )
{
}
}
void print()
{
ofstream g("xormax.out");
cout << maxim << " " << stanga << " " << dreapta << "\n";
g.close();
}
int main()
{
read();
solve();
print();
return 0;
}