Cod sursa(job #2816675)

Utilizator Vlad_AnicaAnica-Popa Vlad-Ioan Vlad_Anica Data 11 decembrie 2021 21:03:03
Problema Xor Max Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.78 kb
#include <iostream>
#include <stdio.h>

using namespace std;
const int SIGMA = 2, MAXDEPTH = 21;

struct trie
{
    trie *e[SIGMA];
    trie()
    {
        for (int i = 0; i < SIGMA; i++)
            e[i] = NULL;
    }
};

void getBits(int nr, char bits[]);
void trie_insert(trie *node, char *bit);
int trie_runthrough(trie *node, int depth, char *bit);


int main()
{
    char bits[MAXDEPTH + 2];
    int nr, maxx, i, n, xorcurr;
    trie *root = new trie();

    FILE *fin = fopen("xormax.in", "r");

    for (i = 0; i <= MAXDEPTH; i++)
        bits[i] = 0;
    bits[MAXDEPTH + 1] = -1;
    trie_insert(root, bits);

    fscanf(fin, "%d", &n);
    maxx = -1;
    xorcurr = 0;
    for (i = 0; i < n; i++)
    {
        fscanf(fin, "%d", &nr);
        getBits(nr, bits);
        maxx = max(maxx, trie_runthrough(root, 0, bits));
        xorcurr ^= nr;
        getBits(xorcurr, bits);
        trie_insert(root, bits);
    }
    fclose(fin);

    FILE *fout = fopen("xormax.out", "w");
    fprintf(fout, "%d", maxx);
    fclose(fout);

    return 0;
}

void getBits(int nr, char bits[])
{
    for (int nrbit = MAXDEPTH; nrbit >= 0; nrbit--)
    {
        bits[nrbit] = nr & 1;
        nr >>= 1;
    }
    bits[MAXDEPTH + 1] = -1;
}
void trie_insert(trie *node, char *bit)
{
    if (*bit == -1)
        return;
    if (node -> e[*bit] == NULL)
        node -> e[*bit] = new trie();
    trie_insert(node -> e[*bit], bit + 1);
}
int trie_runthrough(trie *node, int depth, char *bit)
{
    if (*bit == -1)
        return 0;
    if (node -> e[!(*bit)] != NULL)
        return (1 << (MAXDEPTH - depth)) + trie_runthrough(node -> e[!(*bit)], depth + 1, bit + 1);
    return trie_runthrough(node -> e[*bit], depth + 1, bit + 1);
}