Cod sursa(job #3140655)

Utilizator ciacliboiiiciacli stefan ciacliboiii Data 8 iulie 2023 10:51:47
Problema Xor Max Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.09 kb
#include <bits/stdc++.h>

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

struct Trie {
  int poz;
  Trie* next[2];

  Trie() : poz(0), next{} {}
};

int l, r, s[100001], n, a[100001], ans = -1, cauta, Max = -1;

int Find(Trie* root, int w) {
  for (int i = 20; i >= 0; --i) {
    int c = (w >> i) & 1;
    if (root->next[1 - c] != nullptr)
      root = root->next[1 - c];
    else
      root = root->next[c];
  }
  return root->poz;
}
void Add(Trie* root, int w, int ind) {
  for (int i = 20; i >= 0; --i) {
    int c = (w >> i) & 1;
    if (root->next[c] == nullptr)
      root->next[c] = new Trie();
    root = root->next[c];
  }
    root->poz = ind;
}
int main() {
  fin >> n;
  Trie* root = new Trie();
  Add(root, 0, 0);
  for (int i = 1; i <= n; ++i) {
    fin >> a[i];
    s[i] = s[i - 1] ^ a[i];
    cauta = Find(root, s[i]);
    ans = s[i] ^ s[cauta];
    if (ans > Max) {
      Max = ans;
      l = cauta + 1;
      r = i;
    }
    Add(root, s[i], i);

  }
  fout << Max << ' ' << l << ' ' << r << '\n';
  return 0;
}