Cod sursa(job #3354250)

Utilizator aspaAlexandru Valentin Grigorescu aspa Data 16 mai 2026 22:35:51
Problema Xor Max Scor 30
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.36 kb
#include <bits/stdc++.h>
using namespace std;

struct TrieNode{
    string val;
    TrieNode *parent = nullptr;
    unordered_map<string, TrieNode*> children;

    TrieNode() = default;
    TrieNode(string val) : val(val) {}
};

class Trie{
    TrieNode *root = new TrieNode(" ");

public:
    void insert(vector<string> s, int index){
        int i = 0;
        TrieNode *comp = root;
        while(i < s.size() && comp->children.find(s[i]) != comp->children.end()){ 
            comp = comp->children[s[i]];
            i++;
        }

        while(i < s.size()){
            comp->children[s[i]] = new TrieNode(s[i]);
            comp->children[s[i]]->parent = comp;
            comp = comp->children[s[i]];
            i++;
        }
        
        comp->children["#" + to_string(index)] = nullptr;
    }

    string find(vector<string> bin){
        int i = 0;
        TrieNode *comp = root;

        while(i < 21){
            string opposite = to_string(!stoi(bin[i]));
            string same = to_string(stoi(bin[i]));

            if(comp->children.find(opposite) != comp->children.end()){
                comp = comp->children[opposite];
            }
            else if(comp->children.find(same) != comp->children.end()){
                comp = comp->children[same];
            }
            
            i++;
        }

        for(const auto &x : comp->children){
            return x.first;
        }

        return "-1";
    }
};


int main(){
    ifstream fin("xormax.in");
    ofstream fout("xormax.out");
    
    int n;
    unsigned long long val;
    fin>>n;

    vector<unsigned long long> prefix_xor(n+1);
    vector<string> bin(21, "0");
    Trie trie;
    prefix_xor[0] = 0;
    unsigned long long temp_max = 0, ind_max, ind_min, max = 0;

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

        val = prefix_xor[i];
        int j = 20;
        temp_max = 0;
        while(val && j >= 0){
            bin[j] = '0' + val%2;
            val /= 2;
            j--;
        }
        trie.insert(bin, i);
        string ind = trie.find(bin);
        ind[0] = ' ';
        j = stoi(ind);
        temp_max = prefix_xor[i] ^ prefix_xor[j];
        if(temp_max > max){
            max = temp_max;
            ind_max = i, ind_min = j+1;
        }
        bin.assign(21, "0");
    }


    fout<<max<<" "<<ind_min<<" "<<ind_max;

    return 0;
}