Cod sursa(job #3352601)

Utilizator matei__bBenchea Matei matei__b Data 29 aprilie 2026 12:54:50
Problema Xor Max Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.14 kb
/*


*/

#include <fstream>
#include <vector>

const int NMAX=100'008;

class trie {
private:
    struct nodd {
        int st,dr;
        int pos;
        nodd() : st(-1), dr(-1), pos(0) {}
    };

    std::vector<nodd> v;

public:

    trie() {
        v.push_back(nodd());
    }

    void insert(int x,int idx) {
        int nod=0;
        for(int bit=20; bit>=0; bit--) {
            if(x&(1<<bit)) {
                if(v[nod].dr==-1) {
                    v.push_back(nodd());
                    v[nod].dr=(int)v.size()-1;
                }
                nod=v[nod].dr;
            }
            else {
                if(v[nod].st==-1) {
                    v.push_back(nodd());
                    v[nod].st=(int)v.size()-1;
                }
                nod=v[nod].st;
            }
        }
        v[nod].pos=idx;
    }

    int best(int x,int &idx) {
        int ans=0;
        int nod=0;
        for(int bit=20; bit>=0; bit--) {
            if(x&(1<<bit)) {
                if(v[nod].st!=-1) {
                    ans|=(1<<bit);
                    nod=v[nod].st;
                }
                else {
                    nod=v[nod].dr;
                }
            }
            else {
                if(v[nod].dr!=-1) {
                    ans|=(1<<bit);
                    nod=v[nod].dr;
                }
                else {
                    nod=v[nod].st;
                }
            }
        }
        idx=v[nod].pos;
        return ans;
    }
};

int n;
int a[NMAX];

int main() {
    std::ifstream fin("xormax.in");
    std::ofstream fout("xormax.out");

    fin >> n;
    for(int i=1; i<=n; i++) {
        fin >> a[i];
    }

    int ans=-1,st=0,dr=0;
    int pref=0;
    trie v;
    v.insert(pref,0);
    for(int i=1; i<=n; i++) {
        pref^=a[i];

        int pos=0;
        int cand=v.best(pref,pos);

        if(cand>ans) {
            ans=cand;
            dr=i;
            st=pos+1;
        }

        v.insert(pref,i);
    }

    fout << ans << " " << st << " " << dr << "\n";

    fin.close();
    fout.close();
    return 0;
}