Cod sursa(job #2217628)

Utilizator alextodoranTodoran Alexandru Raul alextodoran Data 1 iulie 2018 11:30:57
Problema Xor Max Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.49 kb
#include <bits/stdc++.h>

using namespace std;

const int N_MAX = 100000;
const int BITS = 21;
const int MAX_VAL = (1 << BITS) - 1;


struct TrieNode {
  TrieNode* sons[2];
  int ind;

  TrieNode() {
    sons[0] = sons[1] = NULL;
    ind = 0;
  }
};

TrieNode* Root = new TrieNode();

int n;
int v[1 + N_MAX];
int xp[1 + N_MAX];
int xormax = -1, startmax, stopmax;

void trieInsert(TrieNode* Node, const int nr, const int index)
{
  for (int bit = BITS - 1; bit >= 0; bit--) {
    if (Node->sons[(nr >> bit) & 1] == NULL)
      Node->sons[(nr >> bit) & 1] = new TrieNode();
    Node = Node->sons[(nr >> bit) & 1];
  }
  Node->ind = index;
}

int trieQuery(TrieNode* Node, const int nr)
{
  for (int bit = BITS - 1; bit >= 0; bit--) {
    if (Node->sons[(nr >> bit) & 1] != NULL)
      Node = Node->sons[( nr >> bit) & 1];
    else
      Node = Node->sons[(~nr >> bit) & 1];
  }
  return Node->ind;
}

int main() {
  ifstream fin ("xormax.in");
  ofstream fout ("xormax.out");
  fin >> n;
  xp[0] = 0;
  for(int i = 1; i <= n; i++) {
    fin >> v[i];
    xp[i] = xp[i - 1] ^ v[i];
  }
  trieInsert(Root, xp[0], 0);
  for(int i = 1; i <= n; i++) {
    int xorComp = MAX_VAL ^ xp[i];
    int j = trieQuery(Root, xorComp);
    int Xor = xp[i] ^ xp[j];
    if(Xor > xormax)
    {
      xormax = Xor;
      startmax = j + 1;
      stopmax = i;
    }
    trieInsert(Root, xp[i], i);
  }
  fout << xormax << " " << startmax << " " << stopmax << '\n';
  return 0;
}