Cod sursa(job #2730354)

Utilizator popashtefan10Popa Stefan popashtefan10 Data 26 martie 2021 10:12:34
Problema Xor Max Scor 75
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2 kb
#include <iostream>
#include <cstdio>

using namespace std;

const int LOGX = 20;
const int NMAX = 100000;

class nod {
public:
  int dr;
  nod *fii[2];

  nod() {
    dr = 0;
    fii[0] = fii[1] = nullptr;
  }
};

class trie {
private:
  nod *root;

public:
  trie() {
    root = new nod;
  }

  void add_nr(int nr, int dr) {
    nod *crt_root = root;

    for(int p2 = 1 << LOGX; p2 > 0; p2 >>= 1) {
      int bit = (nr & p2) == 0 ? 0 : 1;
      if(!crt_root->fii[bit])
        crt_root->fii[bit] = new nod;
      crt_root = crt_root->fii[bit];
    }
    crt_root->dr = dr;
  }

  int get_xor_max(int nr, int &dr) {
    int ret = 0;
    nod *crt_root = root;

    for(int p2 = 1 << LOGX; p2 > 0; p2 >>= 1) {
      int best = ((nr & p2) ^ p2) == 0 ? 0 : 1;
      if(!crt_root->fii[best])
        best = 1 - best;
      ret |= (p2 * best);
      crt_root = crt_root->fii[best];
    }
    dr = crt_root->dr;

    return ret;
  }
};

int xor_prefix[NMAX + 5];

int main() {
  freopen("xormax.in", "r", stdin);
  freopen("xormax.out", "w", stdout);
  int n, xor_all = 0;
  trie tr;

  scanf("%d", &n);
  for(int i = 1; i <= n; i++) {
    scanf("%d", &xor_prefix[i]);
    xor_prefix[i] ^= xor_prefix[i - 1];
  }

  xor_all = xor_prefix[n + 1] = xor_prefix[n];

  int xor_sufix = 0, xor_max = -1, max_st = 0, max_dr = 0;
  for(int l = n - 1; l >= 0; l--) {
    xor_sufix ^= (xor_prefix[l + 2] ^ xor_prefix[l + 1]); /// adaug la sufix nr din sirul initial de pe pozitia l + 2
    tr.add_nr(xor_sufix, l + 2);

    int crt_dr;
    int xor_right = xor_all ^ xor_prefix[l]; /// xor_right = suma ^ pt nr din sirul initial de pe poz l+1 ... n
    int xor_crt = xor_right ^ tr.get_xor_max(xor_right, crt_dr); /// caut sufixul pt care xor_right ^ sufix este maxim

    if(xor_crt > xor_max || (xor_crt == xor_max && crt_dr - 1 < max_dr) )
      xor_max = xor_crt, max_st = l + 1, max_dr = crt_dr - 1;
  }

  printf("%d %d %d", xor_max, max_st, max_dr);

  return 0;
}