Cod sursa(job #2786340)

Utilizator euyoTukanul euyo Data 20 octombrie 2021 19:01:54
Problema Xor Max Scor 75
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.28 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 ) {
  while ( sh ) {
	int bit = (s[pos] >> (sh - 1)) & 1;
    if ( node -> nxt[bit] == NULL ) {
	  node -> nxt[bit] = new Node;
    }
    node = node -> nxt[bit];
    --sh;
  }
  node -> index = pos;
}

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

int main() {
  int n, x, mx = -1;
  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;
	}
  }
  if ( l == r ) {
	fout << mx << " " << l << " " << r; 
  } else {
    fout << mx << " " << l + 1 << " " << r;
  }
  fin.close();
  fout.close();
  return 0;
}