Cod sursa(job #2305679)

Utilizator tifui.alexandruTifui Ioan Alexandru tifui.alexandru Data 20 decembrie 2018 20:21:39
Problema Xor Max Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.08 kb
#include <bits/stdc++.h>

using namespace std;

ifstream f("xormax.in");
ofstream g("xormax.out");

class Trie
{
    private:
        struct TrieNode
        {
            int index=0;
            TrieNode *sons[2]={nullptr,nullptr};
        };

        TrieNode *root=new TrieNode;

    public:

        void _add(const deque <int> &dq,const int &idx)
        {
            TrieNode *current_node=root;
            for(const auto &it:dq)
                if(current_node->sons[it])
                    current_node=current_node->sons[it];
                else
                {
                    current_node->sons[it]=new TrieNode;
                    current_node=current_node->sons[it];
                }

            current_node->index=idx;
        }

        pair <int,int> _find(const deque <int> &dq)
        {
            int ans=0;
            TrieNode *current_node=root;
            for(const auto &it:dq)
                if(current_node->sons[it^1])
                {
                    current_node=current_node->sons[it^1];
                    ans=(ans<<1)+(it^1);
                }
                else
                {
                    current_node=current_node->sons[it];
                    ans=(ans<<1)+it;
                }

            return make_pair(ans,current_node->index);
        }
};

int main()
{
    int best=-1,_begin,_end,i,n,x,xor_sum=0;
    deque <int> dq;
    Trie T;

    for(i=1;i<=20;i++)
        dq.push_back(0);
    T._add(dq,0);

    f>>n;
    for(i=1;i<=n;i++)
    {
        f>>x;
        xor_sum^=x;

        dq.clear();
        int _cpy=xor_sum;
        while(_cpy)
        {
            dq.push_front(_cpy&1);
            _cpy>>=1;
        }
        while(dq.size()<20)
            dq.push_front(0);

        pair <int,int> res=T._find(dq);

        if(res.first^=xor_sum>best)
        {
            best=res.first^=xor_sum;
            _begin=res.second+1;
            _end=i;
        }

        T._add(dq,i);
    }


    g<<best<<' '<<_begin<<' '<<_end;

    return 0;
}