Cod sursa(job #3154157)

Utilizator CelestinNegraru Celestin Celestin Data 3 octombrie 2023 15:10:22
Problema Xor Max Scor 10
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.9 kb
#include <iostream>
#include <fstream>
#include <bitset>
#define size 21
#define sigma 2
using namespace std;
int xormax, start, stop, n, xorsum, x;
struct Trie{
    int cheie, pozitie;
    Trie*fiu[sigma];
    Trie()
    {
        this->cheie=0;
        this->pozitie=0;
        this->fiu[0]=nullptr;
        this->fiu[1]=nullptr;
    }
};
Trie*ROOT=new Trie();
ifstream f("xormax.in");
ofstream g("xormax.out");
void insert(Trie*r,bitset<size> B,int i,int numar,int pozitie)
{
      if(i<0)
      {
          r->cheie=numar;
          if(pozitie>r->pozitie)
             r->pozitie=pozitie;
      }
      else{
          int k=B[i];
          if(r->fiu[k]==nullptr)
              r->fiu[k]=new Trie();
          insert(r->fiu[k],B,i-1,numar,pozitie);
      }
}
void query(Trie*r,bitset<size> B,int i,int&ans,int&poz)
{
    if(i<0)
    {
        ans=r->cheie;
        poz=r->pozitie;
    }
    else{
        int k=B[i];
        if(k==0) {
            if (r->fiu[1] != nullptr)
                query(r->fiu[1], B, i - 1, ans, poz);
            else
                if(r->fiu[0]!=nullptr)
                    query(r->fiu[0], B, i - 1, ans, poz);
        }
        else{
            if (r->fiu[0] != nullptr)
                query(r->fiu[0], B, i - 1, ans, poz);
            else
                if(r->fiu[1]!=nullptr)
                    query(r->fiu[1], B, i - 1, ans, poz);
        }
    }
}
int main()
{
    f>>n;
    f>>x;
    xorsum=x;
    xormax=xorsum;
    start=1;
    stop=1;
    bitset<size> B=0;
    insert(ROOT,B,20,0,0);
    B=xorsum;
    insert(ROOT,B,20,xorsum,1);
    for(int i=2;i<=n;i++)
    {
        f>>x;
        xorsum^=x;
        B=xorsum;
        int ans=0,poz=0;
        query(ROOT,B,20,ans,poz);
        if(xorsum^ans>xormax)
        {
            xormax=xorsum^ans;
            start=poz+1;
            stop=i;
        }
        insert(ROOT,B,20,xorsum,i);
    }
    g<<xormax<<" "<<start<<" "<<stop;
    return 0;
}