Cod sursa(job #2488797)

Utilizator ardutgamerAndrei Bancila ardutgamer Data 7 noiembrie 2019 17:20:56
Problema Xor Max Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.32 kb
#include <cstdio>
#include <algorithm>
#include <climits>

using namespace std;

const int NMAX = 100005;
int v[NMAX];

struct trie{
trie *bit[2];
int nr;
trie()
{
    nr = 0;
    bit[0] = bit[1] = nullptr;
}
};

trie *rad = new trie();

void Add(trie *nod,int i,int &x)
{
    if(i == -1)
    {
        nod->nr = x;
        return;
    }
    bool b = ((1<<i)&x);
    if(b>0) b = 1;
    if(nod->bit[b] == nullptr)
        nod->bit[b] = new trie();
    Add(nod->bit[b],i-1,x);
}

int reckonformax(trie *nod,int i,int &x)
{
    if(i == -1)
        return x^(nod->nr);
    bool b = (1<<i)&x;
    if(b>0) b = 1;
    if(nod->bit[!b])
        return reckonformax(nod->bit[!b],i-1,x);
    else
        return reckonformax(nod->bit[b],i-1,x);
}

int main()
{
    freopen("xormax.in","r",stdin);
    freopen("xormax.out","w",stdout);
    int n,x,pos=1;
    int ma = INT_MIN;
    scanf("%d",&n);
    for(int i = 1 ; i <= n ; i++)
    {
        scanf("%d",&v[i]);
        v[i] ^= v[i-1];
        Add(rad,24,v[i]);
        int cr = reckonformax(rad,24,v[i]);
        if(cr > ma)
        {
            ma = cr;
            pos = i;
        }
    }
    int st = 1;
    for(int i = pos ; i > 0 && (v[pos]^v[i]) != ma ; i--)
        st = i;
    printf("%d %d %d\n",ma,st,pos);
    return 0;
}