Cod sursa(job #2897276)

Utilizator RobertAcAcatrinei Robert-Marian RobertAc Data 3 mai 2022 10:59:42
Problema Xor Max Scor 90
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.95 kb
/******************************************************************************

Welcome to GDB Online.
GDB online is an online compiler and debugger tool for C, C++, Python, PHP, Ruby, 
C#, VB, Perl, Swift, Prolog, Javascript, Pascal, HTML, CSS, JS
Code, Compile, Run and Debug online from anywhere in world.

*******************************************************************************/
#include <bits/stdc++.h>
 
using namespace std;
 
ifstream in("xormax.in");
ofstream out("xormax.out");
 
const int nmax = 100005;
const int nrmax = (1<<22)+5;
/*
struct trie
{
    trie * f[2];
    int i;
    trie(int i=0)
    {
        f[0]=f[1]=nullptr;
        this->i=i;
    }
    void add(int nr,int ind,int poz=22)
    {
        i=ind;
        if(poz==-1)return;
        bool bit=nr&(1<<poz);
        if(f[bit]==nullptr)f[bit]=new trie();
        f[bit]->add(nr,ind,poz-1);
    }
    int query(int nr,int poz=22)
    {
        if(poz==-1)return i;
        bool bit=nr&(1<<poz);
        if(f[bit]!=nullptr)return f[bit]->query(nr,poz-1);
        return f[!bit]->query(nr,poz-1);
    }
} *root = new trie();
*/
int trie[nrmax];
bool exista[nrmax];
 
void add(int nr,int ind,int poz=22,int nod=0)
{
    if(poz==-1)return;
    int bit=nr&(1<<poz);
    nod|=bit;
    trie[nod]=ind;
    exista[nod]=1;
    add(nr,ind,poz-1,nod);
}
 
int query(int nr,int poz=22,int nod=0)
{
    if(poz==-1)return trie[nod];
    int bit=nr&(1<<poz);
    if(exista[nod|bit])return query(nr,poz-1,nod|bit);
    else
    {
        bit=(~(nr&(1<<poz)))&(1<<poz);
        return query(nr,poz-1,nod|bit);
    }
}
 
int sum[nmax];
int n;
 
int main()
{
    in>>n;
    add(0,0);
    int maxx=-1,start,stop;
    for(int i=1;i<=n;i++)
    {
        int nr;
        in>>nr;
        sum[i]=sum[i-1]^nr;
        int ind=query(~sum[i]);
        if((sum[i]^sum[ind])>maxx)
        {
            maxx=sum[i]^sum[ind];
            start=ind+1;
            stop=i;
        }
        add(sum[i],i);
    }
    out<<maxx<<' '<<start<<' '<<stop;
}