Cod sursa(job #2786354)

Utilizator euyoTukanul euyo Data 20 octombrie 2021 19:31:34
Problema Xor Max Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.16 kb
#include <fstream>
#include <iostream>
#include <algorithm>

using namespace std;

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

const int MAXN = 100005; 
const int MAX = 4200000;
const int MAXB = 21;

int T[MAX];
int s[MAXN];

int pos;

inline void insertt() {
  int node = 1;
  T[node] = 0;
  for ( int sh = MAXB; sh > 0; --sh ) {
    node = 2 * node + ((s[pos] >> (sh - 1)) & 1);
	T[node] = 0;
  }
  T[node] = pos;
}

inline int searcht() {
  int node = 1;
  for ( int sh = MAXB; sh > 0; --sh ) {
    int bit = (s[pos] >> (sh - 1)) & 1;
    if ( T[2 * node + (bit ^ 1)] != -1 ) {
	  node = 2 * node + (bit ^ 1);
	} else {
      node = 2 * node + bit; 
	}
  }
  return T[node];
}

int main() {
  int n, x, mx = -1;
  int l = 0, r = 0;

  fin >> n;
  insertt();
  for ( int i = 1; i < MAX; ++i ) {
	T[i] = -1;
  }
  for ( int i = 1; i <= n; ++i ) {
    fin >> x;
	s[i] = s[i-1] ^ x;

	pos = i;
	insertt();
    x = searcht();
	if ( (s[i] ^ s[x]) > mx ) {
      mx = (s[i] ^ s[x]);
	  l = x;
	  r = i;
	}
  }
  if ( l == r ) {
	fout << mx << " " << l << " " << r; 
  } else {
    fout << mx << " " << l + 1 << " " << r;
  }
  fin.close();
  fout.close();
  return 0;
}