Cod sursa(job #3364269)

Utilizator JenJenCristache Ion JenJen Data 31 august 2026 21:31:55
Problema Xor Max Scor 70
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.31 kb
#include <fstream>
using namespace std;

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

int n;
int x[100005];
int trie[(1 << 22)];
bool bit[22];

int st, dr;
int maxx = -1;
int main()
{
    cin >> n;

    for (int i = 1; i <= n; i++)
    {
        cin >> x[i];
    }

    for (int i = 0; i < (1 << 22); i++)
    {
        trie[i] = -1;
    }

    for (int i = 0; i <= 21; i++)
    {
        trie[(1 << i)] = 0;
    }

    for (int i = 2; i <= n; i++)
    {
        x[i] = x[i] ^ x[i - 1];

        for (int j = 0; j < 21; j++)
        {
            bit[j] = (bool)(x[i] & (1 << (20 - j)));
        }

        int poz = 1;
        for (int j = 0; j < 21; j++)
        {
            if (trie[(poz << 1) + 1 - bit[j]] != -1)
            {
                poz = (poz << 1) + 1 - bit[j];
            } else
            {
                poz = (poz << 1) + bit[j];
            }
        }

        poz = trie[poz];

        if((x[i] ^ x[poz]) > maxx)
        {
            maxx = x[i] ^ x[poz];
            st = poz + 1;
            dr = i;
        }

        poz = 1;

        for (int j = 0; j < 21; j++)
        {
            poz = (poz << 1) + bit[j];
            trie[poz] = i;
        }
    }

    cout << maxx << " " << st << " " << dr;
    return 0;
}