Pagini recente » Cod sursa (job #3326451) | Cod sursa (job #24617) | Cod sursa (job #2806231) | Cod sursa (job #1103740) | Cod sursa (job #3347844)
#include <bits/stdc++.h>
using namespace std;
const string NUMEFISIER="xormax";
ifstream fin(NUMEFISIER+".in");
ofstream fout(NUMEFISIER+".out");
int NB=21;
struct Node{
int lastPos;
Node* f[2];
Node(){
lastPos=0;
f[0]=f[1]=nullptr;
}
};
class Arbore{
Node* root;
Node* add_rec(Node* node, int val, int pos, int nb){
if(node==nullptr)
node=new Node();
nb--;
if(nb==-1){
node->lastPos=pos;
return node;
}
bool bitVal=(val&(1<<nb));
node->f[bitVal]=add_rec(node->f[bitVal], val, pos, nb);
return node;
}
void query_rec(Node* node, int val, int nb, int& smax, int& posmax){
nb--;
if(nb==-1){
smax=0;
posmax=node->lastPos;
return;
}
bool bitVal=(val&(1<<nb));
if(node->f[!bitVal]==nullptr){
query_rec(node->f[bitVal], val, nb, smax, posmax);
}
else{
query_rec(node->f[!bitVal], val, nb, smax, posmax);
smax+=(1<<nb);
}
}
public:
Arbore(){
root=nullptr;
}
void add(int val, int pos){
root=add_rec(root, val, pos, NB);
}
pair<int, int> query(int val){
if(root==nullptr) return make_pair(0, 0);
int x,y;
query_rec(root, val, NB, x, y);
return make_pair(x, y);
}
};
int main()
{
int n;
fin>>n;
int prefix=0,x,smax=-1,st=0,dr=0;
Arbore arb;
for(int i=1; i<=n; i++){
fin>>x;
prefix^=x;
pair<int, int> rez=arb.query(prefix);
if(rez.first>smax){
smax=rez.first;
st=rez.second+1;
dr=i;
}
arb.add(prefix, i);
}
fout<<smax<<' '<<st<<' '<<dr;
return 0;
}