Cod sursa(job #2866736)

Utilizator cadmium_Voicu Mihai-Valeriu cadmium_ Data 9 martie 2022 22:11:26
Problema Xor Max Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.61 kb
#include <bits/stdc++.h>
#warning asta e pentru andu cu trie pe biti
#define EOL -1
using namespace std;
#define cin fin
#define cout fout
ifstream cin("xormax.in");
ofstream cout("xormax.out");

const int nmax = 1e5 + 5; //bounduri ca sa se oftice haterii
int val[nmax]; // vectori ca sa se oftice haterii
namespace Trie {
  struct Trie {
    Trie* bit[2];
    int poz;
    Trie() {
      poz = 1e9;
      memset(bit, 0, sizeof(bit));
    }
  };
  using ts = Trie*;
  ts root = new Trie;
  void insert(int* s, int val, ts node = root) {
    if(s[0] == EOL) {
      node -> poz = val;
      return;
    }
    if(node -> bit[s[0]] == 0)
      node -> bit[s[0]] = new Trie;
    insert(s + 1, val, node -> bit[s[0]]);
  }
  int maxx = -1;
  int lf, rh;
  bool dfs(int i, ts node = root, int iter = 22, int k = 0) {
    if(node == 0)
      return 0;
    if(iter == 0) {
      if(k > maxx)
        maxx = k, rh = i, lf = node -> poz;
      return 1;
    }
    if(dfs(i, node -> bit[(val[i] & (1 << iter - 1)) == 0], iter - 1, (k << 1) | 1))
      return 1;
    return dfs(i, node -> bit[(val[i] & (1 << iter - 1)) > 0], iter - 1, (k << 1));
  }
};
 
int s[40]; // bounduri ca sa se oftice haterii
int main() {
  int n;
  cin >> n;
  for(int i = 0; i <= n; i++) {
    if(i != 0)
      cin >> val[i], val[i] ^= val[i - 1];
    for(int j = 21; j >= 0; j--) {
      s[21 - j] = (val[i] & (1 << j)) > 0;
    }
    if(i != 0)
      Trie::dfs(i);
    s[22] = EOF;
    Trie::insert(s, i);
  }
  if(Trie::lf > Trie::rh)
    swap(Trie::lf, Trie::rh);
  Trie::lf = min(Trie::rh, Trie::lf + 1);
  cout << Trie::maxx << ' ' << Trie::lf << ' ' << Trie::rh << '\n';
}