Cod sursa(job #3351755)

Utilizator luca._.solosluca solos luca._.solos Data 21 aprilie 2026 11:28:08
Problema Xor Max Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.88 kb
#include <bits/stdc++.h>

using namespace std;

const int MAXN = 1e5;

int N, pref = 0, a, mx = 0, L, R;

struct Node {
    int p, e;
    vector <int> next;

    Node() {
        p = 0;
        e = 0;
        next.assign(2, -1);
    }
};

struct Trie {
    vector <Node> t;

    Trie() {
        t.push_back(Node());
    }

    void add(int nr, int id) {
        int u = 0;
        t[u].p++;
        t[u].e = id;

        for (int b = 20; b >= 0; b--) {
            int c = (nr & (1 << b)) >> b;

            if (t[u].next[c] == -1) {
                t[u].next[c] = t.size();
                t.push_back(Node());
            }

            u = t[u].next[c];
            t[u].p++;
            t[u].e = id;
        }
    }

    pair <int, int> caut(int nr) {
        int ans = 0, u = 0;

        for (int b = 20; b >= 0; b--) {
            int c = (nr & (1 << b)) >> b;

            if (t[u].next[c] == -1) {
                if (c == 0) {
                    return {ans, t[u].e};
                }
                else {
                    c = 0;
                }
            }

            ans += (c ? (1 << b) : 0);
            u = t[u].next[c];
        }

        return {ans, t[u].e};
        return {ans, t[u].e};
    }
};

Trie trie;

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

    trie.add(0, 1);

    fin >> N;
    for (int i = 1; i <= N; i++) {
        fin >> a;
        pref ^= a;

        int mask = (1 << 21) - 1;
        mask ^= pref;
        int ans = trie.caut(mask).first;
        int id = trie.caut(mask).second;

        if (pref ^ ans > mx) {
            mx = pref ^ ans;
            R = i;
            L = id;
        }
//        fout << pref << ' ' << ans << '\n';

        trie.add(pref, i + 1);
    }

    fout << mx << ' ' << L << ' ' << R;

    return 0;
}