Cod sursa(job #3230350)

Utilizator Alex_BerbescuBerbescu Alexandru Alex_Berbescu Data 20 mai 2024 18:53:26
Problema Xor Max Scor 15
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.56 kb
#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")
#pragma GCC optimize("fast-math")
#include<bits/stdc++.h>
#define inf 0x3f3f3f
using namespace std;
const int dim = 1e5 + 5;
const int bitu = 20;
int v[dim], sp[dim], n, maxi = -inf, st, dr, sum;
struct trie
{
    int sol;
    trie* node[2];
    trie()
    {
        node[0] = node[1] = NULL;
        sol = 0;
    }
};
void add(int idx, trie*nod)
{
    // adaug in trie bitii lui sp[i]
    for(int j = bitu; j >= 0; --j)
    {
        int nr = ((1 << j) & sp[idx]);
        if(nod->node[nr] == NULL)
        {
            nod->node[nr] = new trie;

        }
        nod = nod->node[nr];
    }
    nod->sol = idx;
}
int solve(int idx, trie *nod)
{
    for(int j = bitu; j >=0 ; --j)
    {
        int nr = ((1 << j) & sp[idx]);
        if(nod->node[1 ^ nr] != NULL)
        {
            nod = nod->node[1^ nr];
        }
        else
        {
            nod = nod->node[nr];
        }
    }
    return nod->sol;
}
ifstream fin("xormax.in");
ofstream fout("xormax.out");
int32_t main(int argc, char * argv[])
{
    fin >> n;
    trie*x;
    x = new trie;
    add(0, x);
    for(int i = 1; i <= n; ++i)
    {
        fin >> v[i];
        sp[i] = (sp[i - 1] ^ v[i]);
    }
    for(int i = 1; i <= n; ++i)
    {
       int vo = solve(i, x);
       if((sp[i] ^ sp[vo]) > maxi)
       {
           st = vo + 1;
           dr = i;
           maxi = (sp[i] ^ sp[vo]);
       }
        add(i, x);
    }
    fout << maxi << " " << st << " " << dr;
    return 0;
}