Cod sursa(job #3354029)

Utilizator TLuca2021Teodorescu Luca Nicolae TLuca2021 Data 14 mai 2026 09:26:02
Problema Xor Max Scor 40
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 3.73 kb
#include<iostream>
#include<vector>
#include<string>
#include<fstream>
using namespace std;
ifstream fin("xormax.in");
ofstream fout("xormax.out");
struct Node{
    char value;
    vector<int> children_index;
    int final;
};
string change_to_bitwise(int number){
    string return_string = "";
    while(number){
        if(number % 2 == 1){
            return_string += '1';
        }
        else{
            return_string += '0';
        }
        number /= 2;
    }
    return return_string;
}
//elementul de pe pozitia 0 este root
void createTrie(const string& chain, vector<Node>& return_vector){
    int parent_index = 0;
    for(int j = chain.size() - 1; j >= 0; j--){
        if(!return_vector[parent_index].children_index.empty()){
            if(return_vector[return_vector[parent_index].children_index[0]].value == chain[j]){
                parent_index = return_vector[parent_index].children_index[0];
            }
            else {
                if(return_vector[parent_index].children_index.size() == 1){
                    return_vector.push_back({chain[j], {}, 0});
                    return_vector[parent_index].children_index.push_back(return_vector.size() - 1);
                    parent_index = return_vector.size() - 1;
                }
                else{
                    parent_index = return_vector[parent_index].children_index[1];
                }
            }
        }
        else{
            return_vector.push_back({chain[j], {}, 0});
            return_vector[parent_index].children_index.push_back(return_vector.size() - 1);
            parent_index = return_vector.size() - 1;
        }
        if(j == 0){
            return_vector[parent_index].final++;
        }
    }
}
int findMaxXOR(const string& chain, vector<Node>& return_vector){
    int parent_index = 0;
    int optimal_xor = 0;

    for (int j = 20; j >= 0; j--){
        char bit_curent = chain[j];
        char bit_dorit = (bit_curent == '1' ? '0' : '1');

        int next_node = -1;
        for (int child_idx : return_vector[parent_index].children_index){
            if (return_vector[child_idx].value == bit_dorit){
                next_node = child_idx;
                break;
            }
        }

        if (next_node != -1){
            optimal_xor += (1 << j);
            parent_index = next_node;
        } 
        else{
            if (!return_vector[parent_index].children_index.empty()){
                parent_index = return_vector[parent_index].children_index[0];
            }
        }
    }
    return optimal_xor;
}
int main(){
    int n;
    fin >> n;
    vector<int> v(n);
    for(int i = 0; i < n; i++){
        fin >> v[i];
    }
    vector<int> values_xor(n);
    values_xor[0] = v[0];
    for(int i = 1; i < n; i++){
        values_xor[i] = values_xor[i - 1] ^ v[i];
    }
    vector<string> chains;
    for(int i = 0; i < n; i++){
        string s = change_to_bitwise(values_xor[i]);
        while(s.size() < 21){
            s += '0';
        }
        chains.push_back(s);
    }
    vector<Node> return_vector;
    return_vector.push_back({'R', {} , 0});
    string zero_chain = change_to_bitwise(0);
    while(zero_chain.size() < 21){
        zero_chain += '0';
    }
    createTrie(zero_chain, return_vector);
    int max_overall = 0, ok_idx = -1;
    for(int i = 0; i < chains.size(); i++){
        int current_max = findMaxXOR(chains[i], return_vector);
        if(current_max > max_overall){
            max_overall = current_max;
            ok_idx = i;
        }
        createTrie(chains[i], return_vector);
    }
    fout << max_overall << " ";
    for(int i = 0; i < ok_idx; i++){
        if((values_xor[i] ^ values_xor[ok_idx]) == max_overall){
            fout << i + 2 << " " << ok_idx + 1<< '\n';
            break;
        }
    }
    return 0;
}