Cod sursa(job #3037724)

Utilizator SerbanCaroleSerban Carole SerbanCarole Data 26 martie 2023 12:25:21
Problema Xor Max Scor 90
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.38 kb
#include <fstream>
#include <vector>
#include <algorithm>
#include <queue>
using namespace std;

const int MAX = 1e5 + 1;

ifstream cin("xormax.in");
ofstream cout("xormax.out");

int s , x , n , counter , asta;

struct Trie{

    Trie * next[2] = {nullptr};

    int poz_start = 0;

    void add( int num , int bitpos = 21){

        if(bitpos < 0){

            poz_start = counter;

            return;
        }

        bool val = (((1<<bitpos)&num)>0);

        if(!next[val]){

            next[val] = new Trie;
        }

        next[val] -> add(num,bitpos-1);
    }

    int query( int num , int bitpos = 21){

        if(bitpos < 0){

            asta = poz_start;

            return 0;
        }

        int val = (((1<<bitpos)&num)>0);

        if(next[1-val]){

            return next[1-val]->query(num,bitpos-1) + (1<<bitpos);

        }else if(next[val]) return next[val]->query(num,bitpos-1);
    }

}t;

int main(){

    cin >> n;

    int maxim = 0 , start , stop;

    t.add(0);

    for(int i = 1 ; i <= n ; i++){

        counter++;

        cin >> x;

        s^=x;

        int val = t.query(s);

        if(val > maxim){

            maxim = val;
            start = asta+1;
            stop = i;
        }

        t.add(s);
    }

    cout << maxim << ' ' << start << ' ' << stop;

    return 0;
}