Cod sursa(job #3351787)

Utilizator luca._.solosluca solos luca._.solos Data 21 aprilie 2026 12:18:45
Problema Xor Max Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.67 kb
#include <bits/stdc++.h>
#pragma Gcc optimize("O3", "unroll-loops")

using namespace std;

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

struct Node {
    int p, e;
    int next[2];

    Node() {
        p = 0;
        e = 0;
        next[0] = next[1] = -1;
    }
};

struct Trie {
    vector <Node> t;

    Trie() {
        t.reserve(100001 * 21);
        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 = 1 - ((nr >> b) & 1);

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

            if (c != ((nr >> b) & 1))
                ans += (1 << b);
            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;

        auto [val, id] = trie.caut(pref);

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

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

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

    return 0;
}