Cod sursa(job #3162117)

Utilizator paaull69Ion Paul paaull69 Data 28 octombrie 2023 13:27:41
Problema Xor Max Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.52 kb
#include <bits/stdc++.h>

using namespace std;
typedef unsigned long long int ll;
#define MOD 1000000009

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

struct trie
{
    int r=0;
    trie *fiu[2] = {0};
};

trie *T = new trie();
void ins(trie *p,char *s,int r)
{
    if(*s=='\n')
    {
        p->r=r;
        return;
    }

    if(p->fiu[*s] != 0)
    {
        ins(p->fiu[*s],s+1,r);
        return;
    }
    p->fiu[*s]= new trie;
    ins(p->fiu[*s],s+1,r);
}

int query(trie *p,char *s)
{
    if(*s=='\n')return p->r;
    bool b= (*s)==1;
    if(p->fiu[!b]==0)
    {
        return query(p->fiu[b],s+1);
    }

    return query(p->fiu[!b],s+1);
}

string tostr(int x)
{
    char t[33]={0},k=31;
    t[32]='\n';
    while(x)
    {
        t[k--]=x%2;
        x/=2;
    }
    string s;
    for(int i=0;i<=32;i++)s.push_back(t[i]);
    return s;
}
int pf[100001];
int main()
{
    int mx=0,n;
    fin >> n;
    for(int i=1;i<=n;i++)
    {
        int x;
        fin >> x;
        pf[i]=pf[i-1]^x;
    }
    mx=pf[1];
    string s;
    char t[33]={0};
    s=tostr(pf[1]);
    for(int i=0;i<=32;i++)t[i]=s[i];
    ins(T,t,1);

    int l=1,r=1;

    for(int i=2;i<=n;i++)
    {
        s=tostr(pf[i]);
        for(int i=0;i<=32;i++)t[i]=s[i];
        ins(T,t,i);

        int l1= query(T,t);
        if(pf[i]^pf[l1] > mx)
        {
            l=l1;
            r=i;
            mx=pf[i]^pf[l1];
        }
    }
    fout << mx << " " << l+1 << " " << r;
}