Cod sursa(job #3143171)

Utilizator charizard2021Soham Samanta charizard2021 Data 27 iulie 2023 23:55:32
Problema Xor Max Scor 90
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.9 kb
#include<bits/stdc++.h>
using namespace std;
struct Trie{
    int leftPos;
    Trie* children[2];
    Trie(){
        leftPos = 0;
        memset(children, 0, sizeof(children));
    }
};
Trie* root = new Trie;
int main(){
    ifstream cin("xormax.in");
    ofstream cout("xormax.out");
    int n;
    cin >> n;
    vector<int> v(1 + n);
    for(int i = 1; i <= n; i++){
        cin >> v[i];
    }
    vector<int> prefXor(1 + n, 0);
    for(int i = 1; i <= n; i++){
        prefXor[i] = prefXor[i - 1] ^ v[i];
    }
    Trie* cur = root;
    for(int j = 20; j >= 0; j--){
        if(cur->children[0] == NULL){
            cur->children[0] = new Trie;
        }
        cur = cur->children[0];
        cur->leftPos = 0;
    }
    int leftAns = 0;
    int rightAns = 0;
    int ans = 0;
    for(int i = 1; i <= n; i++){
        Trie* cur2 = root;
        int val = prefXor[i];
        int valCur = 0;
        for(int j = 20; j >= 0; j--){
            int current;
            if(val & (1 << j)){
                current = 0;
            }
            else{
                current = 1;
            }
            valCur ^= (1 << j);
            if(cur2 -> children[current] == NULL){
                current ^= 1;
                valCur ^= (1 << j);
            }
            cur2 = cur2->children[current];
        }
        if(valCur > ans){
            ans = valCur;
            leftAns = cur2->leftPos + 1;
            rightAns = i;
        }
        Trie* cur3 = root;
        for(int j = 20; j >= 0; j--){
            int current;
            if(prefXor[i] & (1 << j)){
                current = 1;
            }
            else{
                current = 0;
            }
            if(cur3->children[current] == NULL){
                cur3->children[current] = new Trie;
            }
            cur3 = cur3->children[current];
            cur3->leftPos = i;
        }
    }
    cout << ans << " " << leftAns << " " << rightAns << "\n";
}