Cod sursa(job #2872546)

Utilizator ArkhamKnightyMarco Vraja ArkhamKnighty Data 17 martie 2022 13:02:16
Problema Xor Max Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.28 kb
#include <fstream>
#define NMAX 100005
#define MAX_BITS 22

using namespace std;

ifstream cin("xormax.in");
ofstream cout("xormax.out");

int N, tempStart, ans, start = 1, stop = 1;
char bitSet[MAX_BITS];
int v[NMAX], xorSum[NMAX];

struct Trie
{
    int freq, start;
    Trie *fii[2];
};

Trie *trie = new Trie();

void Add(Trie *pos, char *bits)
{
    pos->freq ++;
    if (*bits == '\0')
    {
        pos->start = tempStart;
        return;
    }

    int bit = *bits - '0';

    if (pos->fii[bit] == NULL)
    {
        pos->fii[bit] = new Trie();
    }

    Add(pos->fii[bit], bits + 1);
}
///-------------------------------------
int FindXor(Trie *pos, char *bits)
{
    if (*bits == '\0')
    {
        return pos->start;
    }

    int bit = *bits - '0';
    int otherBit = (bit + 1) % 2;

    if (pos->fii[otherBit] != NULL)
    {
        return FindXor(pos->fii[otherBit], bits + 1);
    }
    else
    {
        return FindXor(pos->fii[bit], bits + 1);
    }
}
///-------------------------------------
void ToBinary(int num)
{
    int bitNum = 0;

    while (num)
    {
        bitSet[bitNum ++] = num % 2 + '0';
        num /= 2;
    }

    for (int i = 0 ; i < bitNum / 2 ; ++ i)
    {
        swap(bitSet[i], bitSet[bitNum - i - 1]);
    }
    int cnt = 1;
    for (int i = bitNum - 1 ; i >= 0 ; -- i)
    {
        bitSet[MAX_BITS - cnt] = bitSet[i];
        cnt ++;
    }

    for (int i = 0 ; i < MAX_BITS - bitNum ; ++ i)
    {
        bitSet[i] = '0';
    }
}
///-------------------------------------
inline void Solution()
{
    ToBinary(0);
    Add(trie, bitSet);

    for (int i = 1 ; i <= N ; ++ i)
    {
        ToBinary(xorSum[i]);
        int foundStart = FindXor(trie, bitSet);
        int tempXor = xorSum[i] ^ xorSum[foundStart];

        if (ans < tempXor)
        {
            ans = tempXor;
            if (foundStart == 0) start = i;
            else start = foundStart + 1;
            stop = i;
        }
        tempStart = i;
        Add(trie, bitSet);
    }
}

int main()
{
    cin >> N;

    for (int i = 1 ; i <= N ; ++ i)
    {
        cin >> v[i];
        xorSum[i] = xorSum[i - 1] ^ v[i];
    }
    Solution();
    cout << ans << ' ' << start << ' ' << stop << '\n';
}