Cod sursa(job #2816773)

Utilizator Asgari_ArminArmin Asgari Asgari_Armin Data 12 decembrie 2021 01:20:23
Problema Xor Max Scor 40
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.74 kb
#include <bits/stdc++.h>

using namespace std;

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

const int BIT = 20;
const int SIGMA = 2;
const int NMAX = 1e5;

int ans, pos;
struct Node {
  int pos;
  vector <Node*> v;

  Node() : v(SIGMA, nullptr) {}
};

struct Trie {
private :
  Node* root_ = nullptr;
  Node* insert_(int number, int bit, Node* node);
  int query_(int number, int bit, Node* node);
public:
  void insert(int number, int bit) { root_ = insert_(number, bit, root_); }
  int query(int number, int bit) { return query_(number, bit, root_); }
};

int v[NMAX + 2];

Node* Trie::insert_ (int number, int bit, Node* node) {
  if( node == nullptr )
    node = new Node();

  if( bit > -1 ) {
    int mbit = number & (1 << bit);
    mbit = mbit > 0 ? 1 : 0;
    node->v[mbit] = insert_(number, bit - 1, node->v[mbit]);
  }
  else if( bit == -1 )
    node->pos = pos;
  return node;
}

int Trie::query_ (int number, int bit, Node* node) {
  if( bit == -1 ) {
    ans = node->pos;
    return 0;
  }

  int mbit = number & (1 << bit);
  mbit = mbit > 0 ? 1 : 0;
  mbit ^= 1;

  if( node->v[mbit] == nullptr )
    mbit ^= 1;

  return (mbit * (1 << bit)) + query_(number, bit - 1, node->v[mbit]);
}

int main() {
  Trie trie;
  int n, xorr, i, rasp, maxx, start, stop;
  fin >> n;

  for( i = 1; i <= n; ++i )
    fin >> v[i];
  trie.insert(0, 20);

  maxx = xorr = 0;
  for( i = 1; i <= n; ++i ) {
    xorr ^= v[i];
    ans = 0;
    rasp = trie.query(xorr, 20);

    if( maxx < (xorr ^ rasp) ) {
      maxx = xorr ^ rasp;
      start = 1 + ans;
      stop = i;
    }

    pos = i;
    trie.insert(xorr, 20);
  }
  fout << maxx << " " << start << " " << stop;
  return 0;
}