Cod sursa(job #1975931)

Utilizator triscacezarTrisca Vicol Cezar triscacezar Data 2 mai 2017 15:13:33
Problema Xor Max Scor 5
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.46 kb
#include <bits/stdc++.h>
#define mex vector<pair<vector<Int>,vector<Int> > >
#define Int long long

using namespace std;
ifstream f("xormax.in");
ofstream g("xormax.out");
Int n,Max,i,j,a[100010];
mex v;
int main()
{
    f>>n;
    for(i=1;i<=n;i++)
    {
        f>>a[i];
        a[i]^=a[i-1];
        Int b=a[i],cnt=0;
        while(b)
            cnt++,b>>=1;
        Max=max(Max,cnt);
    }Max--;
    vector<Int> A1,A0;
    for(i=0;i<=n;i++)
        if(a[i]&(1<<Max))
            A1.push_back(i);
        else
            A0.push_back(i);
    v.push_back({A0,A1});
    for(i=Max-1;i>=0;i--)
    {
        mex aux;
        for(auto it:v)
        {
            vector<Int> a00,a01,a10,a11;
            for(auto that:it.first)
                if(a[that]&(1<<i))
                    a01.push_back(that);
                else
                    a00.push_back(that);
            for(auto that:it.second)
                if(a[that]&(1<<i))
                    a11.push_back(that);
                else
                    a10.push_back(that);
            if(a01.size())
                if(a10.size())
                    aux.push_back({a01,a10});
            if(a00.size())
                if(a11.size())
                    aux.push_back({a00,a11});
        }
        if(aux.size())v=aux;
    }auto it=(*v.begin());
    i=(*it.first.begin());
    j=(*it.second.begin());
    g<<(a[i]^a[j])<<' '<<min(i,j)+1<<' '<<max(i,j);
    return 0;
}