Cod sursa(job #2968375)

Utilizator alexandru.morusAlexandru Morus alexandru.morus Data 20 ianuarie 2023 22:44:11
Problema Xor Max Scor 25
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.79 kb
///Alexandru Morus
#include <bits/stdc++.h>

using namespace std;

ifstream in("xormax.in");
ofstream out("xormax.out");
int poz1,poz2,afs;
struct TrieNode
{
    int frg;
    TrieNode *nxt[2];
    TrieNode()
    {
        this->frg = -1;
        memset(this->nxt,0,sizeof(this->nxt));
    }
};
TrieNode * root = new TrieNode;
void ins(TrieNode * root, int N,int pos)
{
    TrieNode *curr = root;
    for(int bit = 20; bit >= 0; bit--)
    {
        bool now = (N & (1 << bit));
        if(curr->nxt[now] == NULL)
        {
            curr->nxt[now] = new TrieNode;
        }
        curr = curr->nxt[now];
    }
   // if(curr->frg == -1)
    {
        curr->frg = pos;
    }

}
void lookup(TrieNode * root, int N,int dc_fac_asta_cu_viata_mea)
{
    TrieNode *curr = root;
    afs = 0;
    if(dc_fac_asta_cu_viata_mea == 7)
    {
        afs = 0;
    }
    for(int bit = 20; bit >= 0; bit--)
    {
        int now = (N & (1 << bit));
        if(curr == NULL)
        {
            return;
        }
        if(curr->nxt[!now] == NULL)
        {
            curr = curr -> nxt[now];
        }
        else
        {
            curr = curr -> nxt[!now];
            afs |= (1 << bit);
        }
    }
    poz2 = curr -> frg;
}

int main ()
{
    int i,t,n,j,q,x = 0,a,afs1 = 0,poz1denis,poz2denis;
    in >> n;
    ins(root, 0, 0);

    for(i = 1; i <= n; i ++)
    {
        in >> a;
        x = x ^ a;
        ins(root,x,i);
        lookup(root,x,i);
        if(afs1 < afs)
        {
            afs1 = afs;
            poz1denis = poz2;
            poz2denis = i;
        }
    }
    if(afs1 == 0)
    {
        out << "0 1 1";
    }
    else
    {
        out << afs1 << ' ' << poz1denis + 1 << ' ' << poz2denis;
    }
    return 0;
}