Cod sursa(job #3354387)

Utilizator aspaAlexandru Valentin Grigorescu aspa Data 17 mai 2026 19:50:56
Problema Xor Max Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.28 kb
#include <bits/stdc++.h>
using namespace std;

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

    int n, u = 1;
    vector<int> prefix_xor(n + 1, 0);
    vector<int> tree(1 << 22, -1);  

    for (int i = 20; i >= 0; i--){
        u = 2 * u; 
        tree[u] = 0;
    }
    int max_xor = -1;
    int best_start = -1, best_stop = -1;

    for(int i = 1; i <= n; i++){
        int val;
        fin >> val;
        prefix_xor[i] = prefix_xor[i - 1] ^ val;
        int current_pref = prefix_xor[i];

        u = 1; 
        for(int bit_pos = 20; bit_pos >= 0; bit_pos--){
            int bit = (current_pref >> bit_pos) & 1;
            int opposite = 1 - bit;

            if(tree[2 * u + opposite] != -1)
                u = 2 * u + opposite;
            else u = 2 * u + bit;
        }
        
        int j = tree[u];
        int temp_xor = current_pref ^ prefix_xor[j];

        if(temp_xor > max_xor){
            max_xor = temp_xor;
            best_start = j + 1;
            best_stop = i;
        }
        u = 1;
        for(int bit_pos = 20; bit_pos >= 0; bit_pos--){
            int bit = (current_pref >> bit_pos) & 1;
            u = 2 * u + bit;
            tree[u] = i;
        }
    }

    fout<<max_xor<<" "<<best_start<<" "<<best_stop<<"\n";

    return 0;
}