Cod sursa(job #2786322)

Utilizator euyoTukanul euyo Data 20 octombrie 2021 18:29:36
Problema Xor Max Scor 60
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.25 kb
#include <fstream>
#include <iostream>
#include <algorithm>

using namespace std;

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

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

int s[MAXN];

struct Node {
  Node() {
	index = -1;
    nxt[0] = nxt[1] = NULL;
  }  

  int index;
  Node *nxt[2];
};

Node *root;

int pos;
void insertt( Node *node, int sh ) {
  if ( sh == 0 ) {
    node -> index = max( pos, node -> index );
	return;
  }
  int bit = (s[pos] >> (sh - 1)) & 1;
  if ( node -> nxt[bit] == NULL ) {
	node -> nxt[bit] = new Node;
  }
  insertt( node -> nxt[bit], sh - 1 );
}

int searcht( Node *node, int sh ) {
  if ( sh == 0 ) {
    return node -> index;
  }
  int bit = (s[pos] >> (sh - 1)) & 1;
  if ( node -> nxt[bit ^ 1] == NULL ) {
	return searcht( node -> nxt[bit], sh - 1 );	
  }
  return searcht( node -> nxt[bit ^ 1], sh - 1 );
}

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

  fin >> n;
  root = new Node;
  insertt( root, MAXB );
  for ( int i = 1; i <= n; ++i ) {
    fin >> x;
	s[i] = s[i-1] ^ x;
	pos = i;
    
	insertt( root, MAXB );
    x = searcht( root, MAXB );
	if ( (s[i] ^ s[x]) > mx ) {
      mx = (s[i] ^ s[x]);
	  l = x;
	  r = i;
	}
  }
  fout << mx << " " << l + 1 << " " << r;
  fin.close();
  fout.close();
  return 0;
}