Cod sursa(job #2634928)

Utilizator loraclorac lorac lorac Data 12 iulie 2020 18:55:39
Problema Xor Max Scor 55
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.92 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+4],poz[lim+4];
int main()
{
    int n,l=0,r=lim,med;
    in>>n;
    v[0]=0;
    for(int i=1;i<=n;++i)
    {
        in>>v[i];
        v[i]^=v[i-1];
    }
    while(l<r)
    {
        if(r==l+1)
            med=r;
        else med=(l+r)/2;
        bool ok=false;
        for(int i=0;i<=n;++i) poz[v[i]]=0;
        for(int i=1;i<=n and !ok;++i)
        {
            int obj=(v[i]^med);
            if(obj<lim and (poz[obj] or obj==0)) ok=true;
            poz[v[i]]=i;
        }
        if(ok) l=med;
        else r=med-1;
    }
    for(int i=1;i<=n;++i) poz[v[i]]=0;
    for(int i=1;i<=n;++i)
    {
        int obj=(v[i]^l);
        if(obj<lim and (poz[obj] or obj==0)) {out<<l<<' '<<poz[obj]+1<<' '<<i<<'\n';return 0;}
        poz[v[i]]=i;
    }
    return 0;
}