Cod sursa(job #2753337)

Utilizator Alex_tz307Lorintz Alexandru Alex_tz307 Data 22 mai 2021 14:41:23
Problema Xor Max Scor 90
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.37 kb
#include <bits/stdc++.h>

using namespace std;

ifstream fin("xormax.in");
ofstream fout("xormax.out");

const int MAXN = 1e5 + 1;
const int L = 21;
const int SIGMA = 2;

struct node {
  int poz, son[SIGMA];
} emptyNode, trie[MAXN * L * SIGMA];

int nodes, s[MAXN];

void add(int val, int poz) {
  int nod = 0;
  for (int bit = 20; bit >= 0; --bit) {
    bool nxt = (val >> bit) & 1;
    if (trie[nod].son[nxt] == -1) {
      node x = emptyNode;
      x.poz = poz;
      trie[++nodes] = x;
      trie[nod].son[nxt] = nodes;
    }
    nod = trie[nod].son[nxt];
    trie[nod].poz = poz;
  }
}

int main() {
  int N;
  fin >> N;
  emptyNode.son[0] = emptyNode.son[1] = -1;
  trie[0] = emptyNode;
  add(0, 0);
  int ans = -1, l = 1, r = N;
  for (int i = 1; i <= N; ++i) {
    fin >> s[i];
    s[i] ^= s[i - 1];
    int nod = 0;
    for (int bit = 20; bit >= 0; --bit) {
      bool nxt = ((s[i] >> bit) & 1) ^ 1;
      int next_node = trie[nod].son[nxt];
      if (next_node != -1) {
        int poz = trie[next_node].poz;
        int val = s[i] ^ s[poz];
        if (ans < val) {
          ans = val;
          l = poz + 1;
          r = i;
        }
        nod = next_node;
      } else nod = trie[nod].son[nxt ^ 1];
    }
    add(s[i], i);
  }
  fout << ans << ' ' << l << ' ' << r << '\n';
  fin.close();
  fout.close();
  return 0;
}