Pagini recente » Cod sursa (job #3273757) | Cod sursa (job #3270787) | Cod sursa (job #632722) | Cod sursa (job #75920) | Cod sursa (job #3338240)
#include <fstream>
#include <utility>
#define x first
#define y second
using namespace std;
ifstream in("xormax.in");
ofstream out("xormax.out");
typedef pair <int, int> pii;
const int nmax = 1e5, lgmax = 31, maxint = (1 << 30);
int n, a[nmax + 2], xormaxx; pii bestt;
struct prefixnode{
int lastt;
prefixnode *nextt[2];
prefixnode() : lastt(0){
nextt[0] = NULL;
nextt[1] = NULL;
}
};
struct prefixtree{
prefixnode *root;
void updateadd(int xx, int where){
prefixnode *node = root;
for(int b = lgmax; b >= 0; b--){
int bit = !!(xx & (1 << b));
if((node -> nextt[bit]) == NULL)
node -> nextt[bit] = new prefixnode();
node = (node -> nextt[bit]);
(node -> lastt) = where;
}
return;
}
pii queryxormax(int xx){
prefixnode *node = root; pii qry = make_pair(0, maxint);
for(int b = lgmax; b >= 0; b--){
int bit = !!(xx & (1 << b));
if((node -> nextt[bit ^ 1]) != NULL){
node = (node -> nextt[bit ^ 1]);
qry.x |= (1 << b); qry.y = min(qry.y, (node -> lastt));
}else if((node -> nextt[bit]) != NULL){
node = (node -> nextt[bit]);
qry.y = min(qry.y, (node -> lastt));
}
}
return qry;
}
} mytrie;
int main(){
in>>n; mytrie.root = new prefixnode();
for(int i = 1; i <= n; i++){
in>>a[i], a[i] ^= a[i - 1];
}
mytrie.updateadd(0, 0);
for(int i = 1; i <= n; i++){
pii qry = mytrie.queryxormax(a[i]);
mytrie.updateadd(a[i], i);
if(xormaxx < qry.x){
xormaxx = qry.x;
bestt = make_pair(qry.y, i);
}
}
out<<xormaxx<<" "<<(bestt.x + 1)<<" "<<bestt.y<<"\n";
return 0;
}