Cod sursa(job #3365919)

Utilizator LucaMuresanMuresan Luca Valentin LucaMuresan Data 27 septembrie 2026 20:57:11
Problema Xor Max Scor 15
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.47 kb
#include <iostream>
#include <vector>
#include <cassert>
#include <algorithm>

#define debug(x) #x << " = " << x << '\n'
using ll = long long;

int main() {
  std::ios_base::sync_with_stdio(false);
  std::cin.tie(0);
  std::cout.tie(0);

  #ifdef INFOARENA
freopen("xormax.in", "r", stdin);
freopen("xormax.out", "w", stdout);
  #endif

  int n;
  std::cin >> n;
  
  std::vector<int> pref(n + 1, 0);
  for (int i = 1; i <= n; i++) {
    int x;
    std::cin >> x;
    pref[i] = (pref[i - 1] ^ x);
  }

  std::vector<int> order(n);
  for (int i = 0; i < n; i++) {
    order[i] = i;
  }
  std::sort(order.begin(), order.end(), [&](int i, int j) {
    return pref[i] < pref[j];
  });

  std::vector<int> prefs = pref;
  prefs.pop_back();
  std::sort(prefs.begin(), prefs.end());

  int answer = -1;
  int L = -1, R = -1;

  auto chmax = [&](int l, int r) -> void {
    if (l > r) {
      std::swap(l, r);
    }
    int x = pref[r] ^ pref[l];
    if (x > answer) {
      answer = x;
      L = l + 1;
      R = r;
    }  
  };

  for (int i = 1; i <= n; i++) {
    // i e capatul dreapta
    // vreau pref[i] ^ pref[j] sa fie maxim <=>
    // (~pref[i]) ^ pref[j] sa fie minim
    int x = ((1 << 30) - 1) ^ pref[i];
    int p = std::lower_bound(prefs.begin(), prefs.end(), x) - prefs.begin();
    chmax(i, order[p]);
    if (p >= 1) {
      chmax(i, order[p - 1]);
    }
  }
  
  std::cout << answer << ' ' << L << ' ' << R;

  return 0;
}