Cod sursa(job #2730392)

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

using namespace std;

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

class nod {
public:
  int dr;
  bool viz;

  nod() : dr(0), viz(false) {}
};

class trie {
private:
//  nod noduri[100000];
  nod noduri[(1 << (LOGX + 2)) + 100];

public:
  void add_nr(int nr, int dr) {
    int crt_idx = 0;

    for(int p2 = 1 << LOGX; p2 > 0; p2 >>= 1) {
      noduri[crt_idx].viz = true;
      int bit = (nr & p2) == 0 ? 0 : 1;
      crt_idx = (crt_idx << 1) + bit + 1;
    }
    noduri[crt_idx].viz = true;
    noduri[crt_idx].dr = dr;
  }

  int get_xor_max(int nr, int &dr) {
    int ret = 0;
    int crt_idx = 0;

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

    return ret;
  }
};

int main() {
  freopen("xormax.in", "r", stdin);
  freopen("xormax.out", "w", stdout);
  int n, x, xor_prefix, xor_max, max_st, max_dr;
  trie tr;

  scanf("%d", &n);
  xor_prefix = 0;
  xor_max = -1;
  for(int l = 1; l <= n; l++) {
    tr.add_nr(xor_prefix, l - 1);
    scanf("%d", &x);
    xor_prefix ^= x;

    int crt_dr;
    int xor_crt = xor_prefix ^ tr.get_xor_max(xor_prefix, crt_dr); /// caut sufixul pt care xor_prefix ^ prefix este maxim

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

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

  return 0;
}