Cod sursa(job #2290664)

Utilizator DavidLDavid Lauran DavidL Data 26 noiembrie 2018 20:11:35
Problema Xor Max Scor 95
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.79 kb
#include <bits/stdc++.h>
#define int long long
using namespace std;
ifstream fi("xormax.in");
ofstream fo("xormax.out");

const int NMAX = 100005;

int sum[NMAX];
int poz[1LL << 22]; /// bagam (1 << nrbit) la inceput
int n;
int nrbit;

int fNrbiti(int x)
{
    int ans = 0;
    while (x)
    {
        ans++;
        x >>= 1;
    }
    return ans;
}

signed main()
{
    fi >> n;
    for (int i = 1; i <= n; i++)
    {
        int x;
        fi >> x;
        sum[i] = sum[i - 1] ^ x;
    }

    for (int i = 1; i <= n; i++)
        nrbit = max(nrbit, fNrbiti(sum[i]));


    memset(poz, -1, sizeof(poz));
    poz[1LL << nrbit] = 0;

    int rez = -1, stRez, drRez;
    for (int i = 1; i <= n; i++)
    {
        /// vedem pana unde avem prefix bun

        int vreau = (1LL << nrbit);
        int unde = 0;
        for (int j = nrbit - 1; j >= 0; j--)
        {
            /// adaugam pe x & (1 << j)
            int moft = vreau + ((sum[i] & (1LL << j)) ^ (1LL << j));
            if (poz[moft] != -1)
            {
                vreau = moft;
                unde = poz[vreau];
            }
            else if (poz[moft ^ (1LL << j)] != -1)
            {
                /// schimbam bitul (1 << j)
                vreau = moft ^ (1LL << j);
                unde = poz[vreau];
            }
        }

        int aici = sum[i] ^ sum[unde];
        if (aici > rez)
        {
            rez = aici;
            stRez = unde + 1;
            drRez = i;
        }


        /// bagam noile prefixe
        int acum = (1LL << nrbit);
        for (int j = nrbit - 1; j >= 0; j--)
        {
            acum += sum[i] & (1LL << j);
            poz[acum] = i;
        }
    }

    fo << rez << " " << stRez << " " << drRez;

    return 0;
}