Cod sursa(job #2634978)

Utilizator loraclorac lorac lorac Data 12 iulie 2020 20:24:08
Problema Xor Max Scor 85
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.94 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);
        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;
}