Cod sursa(job #3294779)

Utilizator EricDimiericdc EricDimi Data 28 aprilie 2025 12:28:01
Problema Xor Max Scor 90
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.54 kb
#include <bits/stdc++.h>

using namespace std;

ifstream f("xormax.in");
ofstream g("xormax.out");

const int MAX_DIM = 100000;
const int MAX_LOG_2 = 21;

int a[MAX_DIM + 1];
int n, sum, maxSum;
int st, dr;

struct Node {
    int bit, val, idx;
    Node *next[2];
    Node() {
        bit = -1;
        val = 0;
        idx = -1;
        next[0] = next[1] = NULL;
    }

} *root, *crt, *sol;

void insert(int val, int pos) {
    crt = root;
    for (int bit = MAX_LOG_2; bit >= 0; bit--) {
        int id = ((val & (1 << bit)) >> bit);
        if (crt->next[id] == NULL) {
            crt->next[id] = new Node;
            crt->next[id]->bit = id;
        }
        crt = crt->next[id];
    }
    crt->val = val;
    crt->idx = pos;
}

Node *find(int val) {
    crt = root;
    for (int bit = MAX_LOG_2; bit >= 0; bit--) {
        int id = ((val & (1 << bit)) >> bit);
        if (crt->next[id ^ 1] != NULL)
            crt = crt->next[id ^ 1];
        else
            crt = crt->next[id];
    }
    return crt;
}

int main() {
    f >> n;
    for (int i = 1; i <= n; i++)
        f >> a[i];

    root = new Node;
    sum = maxSum = 0;
    st = dr = 0;

    for (int i = 1; i <= n; i++) {
        insert(sum, i - 1);
        sum ^= a[i];
        sol = find(sum);
        if ((sum ^ sol->val) > maxSum) {
            maxSum = (sum ^ sol->val);
            st = sol->idx + 1;
            dr = i;
        }
    }

    g << maxSum << " " << st << " " << dr;

    f.close();
    g.close();
    return 0;
}