Cod sursa(job #2816684)

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

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

struct trie
{
    trie *e[SIGMA];
    int pos;
    trie()
    {
        for (int i = 0; i < SIGMA; i++)
            e[i] = NULL;
        pos = -1;
    }
};
struct mytuple
{
    int mx, f, l;
};

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


int main()
{
    char bits[MAXDEPTH + 2];
    int nr, i, n, xorcurr;
    pair<int, int> mxcur;
    mytuple res;
    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, -1);
    res.mx = -1;

    fscanf(fin, "%d", &n);
    xorcurr = 0;
    for (i = 0; i < n; i++)
    {
        fscanf(fin, "%d", &nr);
        getBits(nr, bits);
        mxcur = trie_runthrough(root, 0, bits);
        if (mxcur.first > res.mx)
            res = {mxcur.first, mxcur.second, i};
        xorcurr ^= nr;
        getBits(xorcurr, bits);
        trie_insert(root, bits, i);
    }
    fclose(fin);

    FILE *fout = fopen("xormax.out", "w");
    fprintf(fout, "%d %d %d", res.mx, res.f + 2, res.l + 1);
    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, int ind)
{
    if (*bit == -1)
    {
        node -> pos = max(ind, node -> pos);
        return;
    }
    if (node -> e[*bit] == NULL)
        node -> e[*bit] = new trie();
    trie_insert(node -> e[*bit], bit + 1, ind);
}
pair<int, int> trie_runthrough(trie *node, int depth, char *bit)
{
    if (*bit == -1)
        return make_pair(0, node -> pos);
    if (node -> e[!(*bit)] != NULL)
    {
        pair<int, int> mypair;
        mypair = trie_runthrough(node -> e[!(*bit)], depth + 1, bit + 1);
        return make_pair((1 << (MAXDEPTH - depth)) + mypair.first, mypair.second);
    }
    return trie_runthrough(node -> e[*bit], depth + 1, bit + 1);

}