Cod sursa(job #2855259)

Utilizator Dragono63Stanciu Rares Stefan Dragono63 Data 22 februarie 2022 11:32:17
Problema Xor Max Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.65 kb
#include <bits/stdc++.h>
#define NMAX 100005
#define MAX_BITS 22

using namespace std;

/*******************************/
// INPUT / OUTPUT

ifstream f("xormax.in");
ofstream g("xormax.out");
/*******************************/
/// GLOBAL DECLARATIONS

int N;
int tempStart;
int 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();
/*******************************/
/// FUNCTIONS

void ReadInput();
void Solution();
void Output();
/*******************************/
///-------------------------------------
inline void ReadInput()
{
    f >> N;

    for (int i = 1 ; i <= N ; ++ i)
    {
        f >> v[i];
        xorSum[i] = xorSum[i - 1] ^ v[i];
    }
}
///-------------------------------------
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);
    }
}
///-------------------------------------
inline void Output()
{
    g << ans << " " << start << " " << stop;
}
///-------------------------------------
int main()
{
    ReadInput();
    Solution();
    Output();
    return 0;
}