Cod sursa(job #1717742)

Utilizator akaprosAna Kapros akapros Data 15 iunie 2016 17:48:58
Problema Xor Max Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.84 kb
#include <bits/stdc++.h>
#define maxN 100002
#define maxL 32
using namespace std;
int n, tsize = 1, st[maxN * maxL], top, v[maxN], s[maxN], ans, val, pos;
int px, py, x[maxN];
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]);
    for (i = 1; i <= n; ++ i)
        scanf("%d", &x[i]);
}
void solve(int i)
{
    a[i] = 1;
    if (a[i - 1] && a[i + 1])
            s[i] = s[i - 1] ^ v[i];
        det_xor(s[i]);
        if (val > ans)
        {
            ans = val;
            px = pos + 1;
            py = i;
        }
        insert(s[i], i);
    }
}
void write()
{
    printf("%d %d %d\n", ans);
}
int main()
{
    int op = n;
    read();
    while (op --)
    {
        solve();
        write();
    }
    return 0;
}