Cod sursa(job #1615657)

Utilizator Darius15Darius Pop Darius15 Data 26 februarie 2016 19:00:05
Problema Xor Max Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.32 kb
#include <fstream>
#include <cstring>

using namespace std;

struct arb {
  arb* s;
  arb* d;
  int i;
};

ifstream fin("xormax.in");
ofstream fout("xormax.out");
int x, n, sx, i, l, s[100001], vmax, b, e, bmax, emax;
arb* a = new arb;

void adauga (arb* nod, int n, int p2) {
  if (n & p2 == 0) { // bitul este 0
    nod->s = new arb;
    if (p2 == 1)
      nod->i = i;
    else
      adauga (nod->s, n, p2 >> 1);
  } else {
    nod->d = new arb;
    if (p2 == 1)
      nod->i = i;
    else
      adauga (nod->d, n, p2 >> 1);
  }
}

int cauta (arb *nod, int p2) {
  if (p2 != 0) {
    if (sx & p2 == 1)
      if (nod->s != NULL)
        return cauta(nod->s, p2 >> 1);
      else
        return cauta(nod->d, p2 >> 1);
    else
      if (nod->d != NULL)
        return cauta(nod->d, p2 >> 1);
      else
        return cauta(nod->s, p2 >> 1);
    if (p2 == 1)
      return nod->i;
  }
}

int main () {
  fin >> n;
  for (i = 1; i <= n; i++) {
    fin >> x;
    sx ^= x;
    s[++l] = sx;
    adauga(a, sx, 1 << 21);
    b = cauta (a, 1 << 21);
    if (x ^ s[b] > vmax)
      vmax = x ^ s[b], bmax = b + 1, emax = i;
    adauga(a, sx, 1 << 21);
  }
  fout << vmax << ' ' << bmax << ' ' << emax;
}

/*

-------b-----e---

a ^ b = c
a ^ c = b
b ^ c = a

1100
1010
----
0110
*/