Pagini recente » Cod sursa (job #2708593) | Cod sursa (job #562063) | Cod sursa (job #2256260) | Cod sursa (job #2259850) | Cod sursa (job #1088650)
#include <fstream>
#include <vector>
#include <bitset>
#include <memory.h>
using namespace std;
const char infile[] = "xormax.in";
const char outfile[] = "xormax.out";
ifstream fin(infile);
ofstream fout(outfile);
const int MAXN = 100005;
const int SIGMA = 2;
const int MAXBITI = 21;
const int oo = 0x3f3f3f3f;
typedef vector<int> Graph[MAXN];
typedef vector<int> :: iterator It;
const inline int min(const int &a, const int &b) { if( a > b ) return b; return a; }
const inline int max(const int &a, const int &b) { if( a < b ) return b; return a; }
const inline void Get_min(int &a, const int b) { if( a > b ) a = b; }
const inline void Get_max(int &a, const int b) { if( a < b ) a = b; }
struct Trie {
int where;
Trie *son[2]; /// SIGMA is the alphabet, where is { 0, 1} ;
Trie() {
where = 0;
memset(son, 0, sizeof(son));
}
};
int N, dp[MAXN], maxXor = -1; /// dp[i] = the xor of the first i-th numbers
Trie * Root = new Trie();
void Insert(Trie *Node, const int where, const int pos, const int nr) {
if(pos == -1) {
Node -> where = where;
return;
}
bool actSon = nr & ( 1 << pos );
if(!Node -> son[actSon])
Node -> son[actSon] = new Trie();
Insert(Node -> son[actSon], where, pos - 1, nr);
}
int Query(Trie *Node, const int &pos, const int &nr) {
if(pos == -1)
return Node->where;
bool actSon = nr & ( 1 << pos );
if(!Node -> son[!actSon])
return Query(Node -> son[actSon], pos - 1, nr);
return Query(Node -> son[!actSon], pos - 1, nr);
}
int main() {
int st, fn;
fin >> N;
Insert(Root, 0, 20, 0);
for(int i = 1 ; i <= N ; ++ i) {
int x;
fin >> x;
dp[i] = dp[i - 1] ^ x;
int pos = Query(Root, 20, dp[i]);
if( ( dp[pos] ^ dp[i]) > maxXor) {
maxXor = (dp[pos] ^ dp[i]);
st = pos + 1;
fn = i;
}
Insert(Root, i, 20, dp[i]);
}
fout << maxXor << ' ' << st << ' ' << fn << '\n';
fin.close();
fout.close();
return 0;
}