Cod sursa(job #2954709)

Utilizator ezluciPirtac Eduard ezluci Data 15 decembrie 2022 09:37:38
Problema Xor Max Scor 10
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.77 kb
#ifdef EZ
   #include "./ez/ez.h"
#else
   #include <bits/stdc++.h>
#endif
#define mp make_pair
#define mt make_tuple
#define ll long long
#define pb push_back
#define fi first
#define se second
using namespace std;
const string FILE_NAME = "xormax";
ifstream fin (FILE_NAME + ".in");
ofstream fout (FILE_NAME + ".out");

const int nMAX = 100e3;

int n;
int v[nMAX + 1];
int sp[nMAX + 1];


class Trie {
public:
   Trie *fii[2] = {nullptr, nullptr};
   int pos = -1; // pozitia in vectorul sp

   void add(Trie *nod, int i, int posbit = 20)
   {
      if (posbit == -1)
      {
         nod->pos = i;
         return;
      }
      
      bool bit = (sp[i] & (1<<posbit));

      if (!nod->fii[bit])
         nod->fii[bit] = new Trie;
      add(nod->fii[bit], i, posbit-1);
   }

   int getBestPos(Trie *nod, int i, int posbit = 20)
   {
      if (posbit == -1)
         return nod->pos;
      
      bool bit = (sp[i] & (1<<posbit));

      if (nod->fii[!bit])
         return getBestPos(nod->fii[!bit], i, posbit-1);
      else
         return getBestPos(nod->fii[bit], i, posbit-1);
   }

} *root = new Trie;

int main()
{
   fin >> n;
   for (int i = 1; i <= n; ++i)
   {
      fin >> v[i];
      sp[i] = (sp[i-1] ^ v[i]);
   }
   
   int max = -1, start, stop;

   root->add(root, 0); // 20 e pozitia bitului maxim
   for (int i = 1; i <= n; ++i)
   {
      int bestpos = root->getBestPos(root, i);
      int val = (sp[i] ^ sp[bestpos]);
      
      if (val > max)
      {
         max = val;
         start = bestpos+1;
         stop = i;
      }
      else if (val == max)
      {
         start = bestpos+1;
         stop = i;
      }

      root->add(root, i);
   }

   fout << max << ' ' << start << ' ' << stop;
}