Cod sursa(job #3351776)

Utilizator luca._.solosluca solos luca._.solos Data 21 aprilie 2026 12:02:14
Problema Xor Max Scor 80
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.65 kb
#include <bits/stdc++.h>

using namespace std;

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

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++;

        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) {
                c = 1 - c;
            }

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

        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;
        auto [ans, id] = trie.caut(mask);
        int val = pref ^ ans;

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

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

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

    return 0;
}