Cod sursa(job #1718210)

Utilizator akaprosAna Kapros akapros Data 16 iunie 2016 23:35:40
Problema Xor Max Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.83 kb
#include <bits/stdc++.h>
#define maxN 100002
#define maxL 23
using namespace std;
int n, tsize = 1, st[maxN * maxL], top, v[maxN], s[maxN], ans, val, pos;
int px, py;
typedef struct
{
    int c[2], p;
    int val;
    int nc;
} trie;
trie t[maxN * maxL];
void insert(int x, int y)
{
    int ind = 1, C, lev = 0;
    for ( ; lev < maxL; ++ lev)
    {
        C = x & (1 << (maxL - lev - 1));
        if (C > 0)
            C = 1;
        if (!t[ind].c[C])
        {
            if (top)
            {
                t[ind].c[C] = st[top];
                -- top;
            }
            else
                t[ind].c[C] = ++ tsize;
            t[t[ind].c[C]].p = ind;
            t[ind].nc = y;
        }
        t[ind].nc = y;
        ind = t[ind].c[C];
    }
    ++ t[ind].val;
}
void det_xor(int x)
{
    int ind = 1, C, lev = 0;
    val = 0;
    for (; lev < maxL; ++ lev)
    {
        C = !(x & (1 << (maxL - lev - 1)));

        if (!t[ind].c[C])
            C = !C;
        else
            val += (1 << (maxL - lev - 1));
        pos = t[ind].nc;
        ind = t[ind].c[C];
    }
    ++ t[ind].val;
}
void read()
{
    int i;
    freopen("xormax.in", "r", stdin);
    scanf("%d", &n);
    ans = -1;
    insert(0, 0);
    for (i = 1; i <= n; ++ i)
        {
            scanf("%d", &v[i]);
            s[i] = s[i - 1] ^ v[i];
        }
}
void solve()
{
    int i;
    for (i = 1; i <= n; ++ i)
    {
        val = 0;
        det_xor(s[i]);
        if (val > ans)
            {
                ans = val;
                px = pos + 1;
                py = i;
            }
        insert(s[i], i);
    }
}
void write()
{
    freopen("xormax.out", "w", stdout);
    printf("%d %d %d\n", ans, px, py);
}
int main()
{
    read();
    solve();
    write();
    return 0;
}