Cod sursa(job #3146592)

Utilizator vladburacBurac Vlad vladburac Data 21 august 2023 19:37:04
Problema Xor Max Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.11 kb
#include <bits/stdc++.h>
using namespace std;
const int NMAX = 1e5;
using ll = long long;

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

int v[NMAX + 1];

struct Node {
    int val;
    int pos;
    Node* leftChild;
    Node* rightChild;
    Node() {
      val = pos = -1;
      leftChild = rightChild = nullptr;
    }
    ~Node() {
      delete leftChild;
      delete rightChild;
    }
};

void insert(Node* root, int val, int pos) {
    int bit;
    for (bit = 20; bit >= 0; bit--) {
      if( (val & (1 << bit)) != 0 ) {
        if( root->rightChild != nullptr )
           root = root->rightChild;
        else {
          root->rightChild = new Node();
          root = root->rightChild;
        }
      }
      else {
        if( root->leftChild != nullptr )
          root = root->leftChild;
        else {
          root->leftChild = new Node();
          root = root->leftChild;
        }
      }
    }
    root->val = val;
    root->pos = max( root->pos, pos );
}

Node* query(Node* root, int xorr) {
  int bit;
  for( bit = 20; bit >= 0; bit-- ) {
    int val = xorr & ( 1 << bit );
    if( val )
      val = 0;
    else val = 1;
    if( ( val == 0 && root->leftChild != nullptr ) || root->rightChild == nullptr )
      root = root->leftChild;
    else
      root = root->rightChild;
  }
  return root;
}
void solve() {
    int n, i, xorr, ans, left, right;
    fin >> n;
    Node* root = new Node();
    Node* aux = nullptr;
    for (i = 0; i < n; i++) {
       fin >> v[i];
    }
    insert(root, 0, 0);
    xorr = 0;
    ans = left = right = -1;
    for (i = 0; i < n; i++) {
      xorr = xorr ^ v[i];
      aux = query(root, xorr);
      if( (aux->val ^ xorr) > ans ) {
        ans = aux->val ^ xorr;
        left = aux->pos + 1;
        right = i + 1;
      }
      insert(root, xorr, i + 1);
    }
    fout << ans << " " << left << " " << right;
}

signed main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    int t = 1;
    //cin >> t;
    while (t--) {
      solve();
    }
    return 0;
}