Cod sursa(job #2626940)

Utilizator CraniXortDumitrescul Eduard CraniXort Data 9 iunie 2020 09:38:00
Problema Xor Max Scor 90
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.43 kb
#include <bits/stdc++.h>

std::ifstream fin ("xormax.in");
std::ofstream fout ("xormax.out");

std::string toString (int nr){
    std::string s;
    for (int i=0; i<22; i++){
        s.push_back ('0' + nr%2);
        nr /= 2;
    }
    std::reverse (s.begin(), s.end());
    return s;
}

class Trie{

struct Node{
    char val;
    int next[2] = {};
};

std::vector <Node> trie;
int size;

public:
    Trie (){
        size = 1;
        trie.clear();
        struct Node node;
        node.val = '#';
        trie.push_back (node);
    }

    void add (std::string s){
        int node = 0, i;
        for (i=0; i<s.size(); i++){
            if (trie[node].next[s[i]-'0'] == 0){
                struct Node newNode;
                newNode.val = s[i] - '0';
                trie.push_back (newNode);
                trie[node].next[s[i]-'0'] = size;
                size ++;
            }

            node = trie[node].next[s[i]-'0'];
        }
    }

    int query (std::string s){
        int node = 0;
        int ans = 0, i, p2=1;
        for (i=0; i<s.size(); i++){
                ans *= 2;
            if (trie[node].next['1'-s[i]] != 0){
                ans ++;
                node = trie[node].next['1'-s[i]];
            }
            else if (trie[node].next[s[i] - '0']){
                node = trie[node].next[s[i]-'0'];
            }
            p2 *= 2;
        }

        return ans;
    }

    void print (){
        for (int i=0; i<trie.size(); i++){
            struct Node node = trie[i];
            fout << trie[i].val << ' ' << trie[i].next[0] << ' ' << trie[i].next[1] << '\n';
        }

    }

};


int main()
{
    int n, i, number, max=0, stop, newVal;
    fin >> n;
    int x[n], Xor[n] = {};
    Trie trie;

    //trie.print();
    trie.add ("0000000000000000000000");
    //trie.print();

    for (i=0; i<n; i++){
        fin >> x[i];
        if (i == 0)
            Xor[i] = x[i];
        else
            Xor[i] = Xor[i-1] ^ x[i];
        newVal = trie.query (toString (Xor[i]));
        if (max < newVal){
            max = newVal;
            stop = i;
        }
        trie.add (toString (Xor[i]));
    }
    //trie.print();
    int start;
    for (i=stop-1; i>=0; i--){
        if ((Xor[stop] ^ Xor[i]) == max){
            start = i;
            break;
        }

    }
    fout << max << ' ' << start +2<< ' ' << stop+1;
    return 0;
}