Cod sursa(job #2815898)

Utilizator iancupoppPopp Iancu Alexandru iancupopp Data 10 decembrie 2021 16:09:50
Problema Xor Max Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.23 kb
#include <fstream>

using namespace std;

const int N = 1e5 + 5;
const int INF = 2e9;
const int P2MAX = 20;

class Nod {
public:
  Nod* fii[2] = {0, 0};
  int poz;
};

class Trie {
private:
  Nod* rad = new Nod;
public:
  void insert(int val, int poz) {
    Nod* nod = rad;
    for (int i = P2MAX; i >= 0; --i) {
      Nod* &nxt = nod->fii[(bool)(val & (1 << i))];
      if (nxt == nullptr)
        nxt = new Nod;
      nod = nxt;
    }
    nod->poz = poz;
  }
  int xormax(int val) {
    Nod* nod = rad;
    for (int i = P2MAX; i >= 0; --i) {
      bool nxt = !(bool)(val & (1 << i));
      if (nod->fii[nxt] == nullptr)
        nxt = !nxt;
      nod = nod->fii[nxt];
    }
    return nod->poz;
  }
};

int x[N];

int main() {
  ifstream cin("xormax.in");
  ofstream cout("xormax.out");
  int n;
  cin >> n;
  Trie t;
  t.insert(0, 0);
  int ans = -1, a, b;
  for (int i = 1; i <= n; ++i) {
    int val;
    cin >> val;
    x[i] = val ^ x[i - 1];
    int poz = t.xormax(x[i]);
    int xr = x[i] ^ x[poz];
    if (xr > ans) {
      ans = xr;
      a = poz + 1, b = i;
    }
    t.insert(x[i], i);
  }
  cin.close();
  cout << ans << " " << a << " " << b << "\n";
  cout.close();
  return 0;
}