Cod sursa(job #3195866)

Utilizator BOSSSTEFANPetrescu Ioan Stefan BOSSSTEFAN Data 21 ianuarie 2024 21:36:42
Problema Xor Max Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.3 kb
#include <fstream>

using namespace std;
ifstream cin("xormax.in");
ofstream cout("xormax.out");
struct trie
{
    int poz;
    trie *fiu[2];
}*root=new trie;
int v[22],i;
const int pow=1<<20;
int val,rez,x,y;
void startup(trie *nod)
{
    nod->fiu[1]=NULL;
    nod->fiu[0]=NULL;
}
void adaug(trie *nod1, trie *nod2, int pas, int p)
{
    if(pas==0)
    {
        nod1->poz=i;
        if(val>rez)
        {
            rez=val;
            x=nod2->poz+1;
            y=i;
        }
        val=0;
    }
    else
    {
        if(nod1->fiu[v[pas]]==NULL)
        {
            nod1->fiu[v[pas]]=new trie;
            startup(nod1->fiu[v[pas]]);
        }
        if(nod2->fiu[1-v[pas]]==NULL)
            nod2=nod2->fiu[v[pas]];
        else
        {
            nod2=nod2->fiu[1-v[pas]];
            val+=p;
        }
        adaug(nod1->fiu[v[pas]],nod2,pas-1,p>>1);
    }
}
int main()
{
    startup(root);
    int n,xp=0,nr,cop,j;
    cin>>n;
    adaug(root,root,21,pow);
    for(i=1;i<=n;i++)
    {
        cin>>nr;
        xp=xp^nr;
        cop=xp;
        for(j=1;j<=21;j++)
        {
            v[j]=cop&1;
            cop>>=1;
        }
        adaug(root,root,21,pow);
    }
    if(y==0)
        x=y=1;
    cout<<rez<<" "<<x<<" "<<y;
    return 0;
}