Cod sursa(job #2971870)

Utilizator PHOSSESSEDProsie Radu-Teodor PHOSSESSED Data 28 ianuarie 2023 11:06:42
Problema Trie Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.45 kb
#include <fstream>
#include<algorithm>
using namespace std;

ifstream fin("xormax.in");
ofstream fout("xormax.out");

int c = 0;

struct Trie
{
    int e = 0,trec = 0;
    Trie *next[2] = {nullptr};

    void baga(int n,int p = 30)
    {
        trec++;
        if(p < 0)
            {
                e = c;
                return;
            }

        int bit = ((n & (1 << p)) > 0) ? 1 : 0;
        if(!next[bit])
            {
                next[bit] = new Trie;
            }

        next[bit]->baga(n,p - 1);
    }

    pair<int,int> best(int x,int p = 30,int pref = 0)
    {
        if(p < 0)
            return {(x ^ pref),e};
        int caut = ((x & (1 << p)) > 0 ? 0 : 1);
        if(next[caut])
            return next[caut]->best(x,p - 1,pref + (1 << p) * caut);
        else return next[caut ^ 1]->best(x,p - 1,pref + (1 << p) * (caut ^ 1));

    }
};


int main()
{

    Trie *trie = new Trie;
    int n,x,ans = 0,suma = 0,st = 0,dr = 1; fin >> n;
    trie->baga(0);
    for(int i = 1; i <= n ; i++)
        {
            fin >> x;
            suma ^= x;
            pair<int,int> local = trie->best(suma);
            if(local.first > ans)
                {
                    ans = local.first;
                    st = local.second;
                    dr = i;
                }

            c = i;
            trie->baga(suma);

        }

    fout << ans << " " << st + 1 << " " << dr;
}