Cod sursa(job #2767084)

Utilizator nstefanNeagu Stefan nstefan Data 4 august 2021 18:32:25
Problema Xor Max Scor 90
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.77 kb

#include <bits/stdc++.h>

#ifdef INFOARENA
#define __OUTPUT_FILE__ fout
#else
#define __OUTPUT_FILE__ std::cout
#endif
#define print(x) __OUTPUT_FILE__ << x
#define read(x) fin >> x
#define debugPrint(x) print(#x << ": " << (x) << '\n')

#define MAXNUMS 100000
#define __NAME_OF_THE_FILE__ "xormax"
typedef unsigned int type;

std::ifstream fin(__NAME_OF_THE_FILE__ ".in");
std::ofstream fout(__NAME_OF_THE_FILE__ ".out");

type n, arr[MAXNUMS + 1];
void setup(), solve(), finish();

const size_t nrBiti = 21;
type max = 0, start = 0, end = 0;
struct Tree {
  // for the left most start index
  // private:
  // bool hasBeenUsed = false;
  // public:
  type index;  // leaf node index
  Tree *children[2];
  Tree() {
    index = 0;
    // bool hasBeenUsed = false;
    children[0] = 0;  // the pointer points to an empty address
    children[1] = 0;  // the pointer points to an empty address
  }

  // moves through the bits of the val (from the most significative to the
  // last significative)
  // and adds them to the trie (a suffix trie to be precise)
  void insert(type val, type index) {
    Tree *node = this;
    for (size_t i = 0; i < nrBiti; i++) {
      bool bit = val & (1 << ((nrBiti - 1) - i));

      if (node->children[bit] == 0) node->children[bit] = new Tree();
      node = node->children[bit];
      if (i == (nrBiti -
                1)) {  // && node->hasBeenUsed == false // left most start index
        node->index = index;
        // hasBeenUsed = true;
      }
    }
  }

  // it searches for a number ( [compl] ) for which [compl] ^ [val] is the
  // greatast as it can be
  // it returns compl->index
  type search(type val) {
    Tree *node = this;
    type index;
    for (size_t i = 0; i < nrBiti; i++) {
      bool bit = val & (1 << ((nrBiti - 1) - i));
      bool invBit = 1 - bit;

      if (node->children[invBit] != 0) {  // if exists
        node = node->children[invBit];
      } else {
        node = node->children[bit];
      }
      if (i == (nrBiti - 1)) {  // if we are on a leaf
        index = node->index;
      }
    }
    return index;
  }
} tree;

int main() {
  std::ios_base::sync_with_stdio(false);
  std::cin.tie(nullptr);
  setup();
  solve();
  finish();

  return 0;
}

// solve the problem (succes jmechere ;)
void solve() {
  for (size_t i = 1; i < n; i++) {
    arr[i] ^= arr[i - 1];
    if (i > 1) {
      type j = tree.search(arr[i]);
      type sumxor = arr[j] ^ arr[i];
      if (sumxor > max) {
        max = sumxor;
        start = j + 1;
        end = i;
      }
    }
    tree.insert(arr[i], i);
  }
}

// read the data from the input file
void setup() {
  read(n);
  n++;
  for (size_t i = 1; i < n; i++) {
    read(arr[i]);
  }
  fin.close();
}

// print the data to the console/file
void finish() {
  print(max << ' ' << start << ' ' << end);
  fout.close();
}