Cod sursa(job #2635004)

Utilizator loraclorac lorac lorac Data 12 iulie 2020 21:28:48
Problema Xor Max Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.14 kb
#include <bits/stdc++.h>
using namespace std;
ifstream in("xormax.in");
ofstream out("xormax.out");
const int nmax=1e5,lim=(1<<21);
int v[nmax+5],ok[lim+5];
bool b[30];
int main()
{
    int n;
    in>>n;
    for(int i=1;i<=n;++i)
    {
        in>>v[i];
        v[i]=(v[i-1]^v[i]);
        ok[v[i]]=1;
    }
    ok[0]=1;
    for(int i=1;i<lim;++i)
        ok[i]+=ok[i-1];
    int maxim=0;
    for(int i=1;i<=n;++i)
    {
        int k=v[i];
        for(int j=0;j<21;++j)
            b[j]=k&1,k>>=1;
        int part=0;
        for(int j=20;j>=0;--j)
        if(!b[j])
        {
            if(ok[part+(1<<(j+1))-1]-ok[part+(1<<j)-1]>0)
                part+=(1<<j);
        }
        else
        {
            if(!((part and ok[part+(1<<j)-1]-ok[part-1]>0) or (!part and ok[part+(1<<j)-1]>0)))
                part+=(1<<j);
        }
        maxim=max(maxim,(part^v[i]));
    }
    out<<maxim<<' ';
    for(int i=0;i<lim;++i) ok[i]=0;
    for(int i=1;i<=n;++i)
    {
        int part=(v[i]^maxim);
        if(part==0 or ok[part]!=0) {out<<ok[part]+1<<' '<<i<<'\n';return 0;}
        ok[v[i]]=i;
    }
    return 0;
}