Cod sursa(job #3338745)

Utilizator parus_majorParus Major parus_major Data 4 februarie 2026 19:31:18
Problema Xor Max Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.46 kb
#include <iostream>
#include <fstream>
#include <algorithm>
#include <vector>
#include <climits>

using namespace std;

ifstream fin("xormax.in");
ofstream fout("xormax.out");

const int MAXLOG = 22;
const int MAXN = 100002;

struct Trie {
    int poz;
    Trie* next[2];
};

int v[MAXN];
int start, finish, ans, N;

void insert(Trie* root, int value, int p) {
    root->poz = p;
    for (int i = MAXLOG - 1; i >= 0; --i) {
        const int bit = (value & (1 << i)) ? 1 : 0;
        if (root->next[bit] == nullptr) {
            root->next[bit] = new Trie();
        }
        root->next[bit]->poz = p;
        root = root->next[bit];
    }
}

int search(Trie* root, int value) {
    for (int i = MAXLOG - 1; i >= 0; --i) {
        const int desired_bit = (value & (1 << i)) ? 0 : 1;
        if (root->next[desired_bit]) {
            root = root->next[desired_bit];
        } else {
            root = root->next[1 - desired_bit];
        }
    }
    return root->poz;
}


int main()
{
    Trie* root = new Trie();
    insert(root, 0, 0);
    ans = INT_MIN;

    fin >> N;
    for (int i = 1; i <= N; ++i) {
        fin >> v[i];
        v[i] ^= v[i - 1];

        int p = search(root, v[i]);
        if (ans < (v[i] ^ v[p])) {
            ans = v[i] ^ v[p];
            start = p + 1;
            finish = i;
        }

        insert(root, v[i], i);
    }

    fout << ans << ' ' << start << ' ' << finish;
    return 0;
}