Cod sursa(job #3347844)

Utilizator TeodorVTeodorV TeodorV Data 18 martie 2026 16:14:45
Problema Xor Max Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.89 kb
#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;
}