Cod sursa(job #3140652)

Utilizator ciacliboiiiciacli stefan ciacliboiii Data 8 iulie 2023 10:41:29
Problema Xor Max Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.29 kb
#include <bits/stdc++.h>

using namespace std;
ifstream fin("xormax.in");
ofstream fout("xormax.out");
struct Trie
{
    int poz;
    Trie* next[2];
    Trie() : poz(0), next{} {}
};
int l, r, s[100001], n, a[100001], ans, cauta, Max;
int Find(Trie* root, int w)
{
    for(int i = 20; i >= 0; -- i)
    {
         int c = (w >> i) & 1;
         if(root -> next[1 - c] != nullptr)
            root = root -> next[1 - c];
        else
            root  = root -> next[c];
    }
    return root -> poz;
}
void Add(Trie *root, int w, int ind)
{
    for(int i = 20; i >= 0; --i)
    {
        int c = (w >> i) & 1;
        if(root -> next[c] == nullptr)
            root -> next[c] = new Trie();
        root = root -> next[c];
    }
    if(root -> poz == 0)
    root -> poz = ind;
}
int main()
{
    fin >> n;
    Trie *root = new Trie();
    for(int i = 1; i <= n; ++ i)
    {
        fin >> a[i];
        s[i] = s[i - 1] ^ a[i];
        if(i > 1)
        {
            cauta = Find(root, s[i]);
            ans = s[i] ^ s[l];
            if(ans > Max)
            {
                Max = ans;
                l = cauta;
                r = i;
            }
        }
        Add(root, s[i], i);

    }
    fout << Max << ' ' << l << ' ' << r << ' ' ;
    return 0;
}