Cod sursa(job #3234040)

Utilizator unomMirel Costel unom Data 6 iunie 2024 09:36:40
Problema Xor Max Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.43 kb
#include <fstream>

using namespace std;

struct trie
{
    trie *fii[2];
    int ind = 0;
};

ifstream in("xormax.in");
ofstream out("xormax.out");
int n;
int ans, st, dr;
int v[100005];
int sp[100005];
trie *t = new trie();

void adauga(trie *p, int poz, int ind)
{
    if(poz == -1)
    {
        p->ind = ind;

        return;
    }

    int bit;
    if(sp[ind] & (1 << poz))
    {
        bit = 1;
    }
    else
    {
        bit = 0;
    }

    if(p->fii[bit] == NULL)
    {
        p->fii[bit] = new trie();
    }

    adauga(p->fii[bit], poz - 1, ind);
}

int cauta(trie *p, int poz, int ind)
{
    if(poz == -1)
    {
        return p->ind;
    }

    //e invers aici
    int bit;
    if(sp[ind] & (1 << poz))
    {
        bit = 0;
    }
    else
    {
        bit = 1;
    }

    if(p->fii[bit] == NULL)
    {
        bit = 1 - bit;
    }

    return cauta(p->fii[bit], poz - 1, ind);
}

int main()
{
    in>>n;

    ans = -(1 << 30);
    for(int i = 1; i<=n; i++)
    {
        in>>v[i];

        sp[i] = sp[i - 1] ^ v[i];
    }

    adauga(t, 30, 0);

    for(int i = 1; i<=n; i++)
    {
        int best = cauta(t, 30, i);

        if((sp[i] ^ sp[best]) > ans)
        {
            ans = sp[i] ^ sp[best];
            st = best + 1;
            dr = i;
        }

        adauga(t, 30, i);
    }

    out<<ans<<" "<<st<<" "<<dr;

    return 0;
}