Cod sursa(job #2972207)

Utilizator velciu_ilincavelciu ilinca velciu_ilinca Data 28 ianuarie 2023 20:54:46
Problema Xor Max Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.87 kb
#include <fstream>

using namespace std;
ifstream in("xormax.in");
ofstream out("xormax.out");

int partial[100005];

class TrieNode
{
private:
    int idx;
    TrieNode *edges[2];

public:
    TrieNode()
        {
            idx=-1;
            for(int i=0;i<2;i++)
            {
                edges[i]=nullptr;
            }
        }

    void insert1(int val,int inidx,int poz)
    {
        if(poz==-1)
        {
            idx=inidx;
            return;
        }
        int bit=((val>>poz)&1);
        if(edges[bit]==nullptr)
        {
            edges[bit]=new TrieNode();
        }
        edges[bit]->insert1(val,inidx,poz-1);
    }

    int find_best_opposite(int val,int poz=21)
    {
        if(poz==-1)
            return idx;
        int bit=((val>>poz)&1);
        if (edges[!bit]!=nullptr)
        {
            return edges[!bit]->find_best_opposite(val,poz-1);
        }
        return edges[bit]->find_best_opposite(val,poz-1);
    }
};
int main()
{
    int n;
    in>>n;
    for (int i=1;i<=n;i++)
    {
        int val;
        in>>val;
        partial[i]=partial[i-1]^val;
    }
    TrieNode root=TrieNode();
    root.insert1(partial[1],1,21);
    if(n==1)
    {
        out<<partial[1]<<' '<<1<<' '<<1<<'\n';
        return 0;
    }
    int maxi=-1;
    int stans,drans;
    for (int i=2;i<=n;i++)
    {
        int st=root.find_best_opposite(partial[i]);
        int possibleans=partial[st]^partial[i];
        if (partial[i]>possibleans && partial[i]>maxi)
        {
            possibleans=partial[i];
            stans=1;
            drans=i;
        }
        else if(possibleans>maxi)
        {
            maxi=possibleans;
            stans=st+1;
            drans=i;
        }
        root.insert1(partial[i],i,21);
    }
    out<<maxi<<' '<<stans<<' '<<drans<<'\n';
    return 0;
}