Cod sursa(job #3161645)

Utilizator AlexandruBenescuAlexandru Benescu AlexandruBenescu Data 27 octombrie 2023 18:47:30
Problema Xor Max Scor 40
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.39 kb
#include <bits/stdc++.h>
#define L 100005
#define BIT_MAX 22
using namespace std;
ifstream fin("xormax.in");
ofstream fout("xormax.out");

int n;
int v[L];

struct NODE {
  int valueCnt;
  int prefixCnt;
};

unordered_map <string, NODE> G;
unordered_map <int, int> pos;

void insertOperation(int x) {
  string path = "";
  for (int bit = BIT_MAX; bit >= 0; bit--) {
    path += ('0' + (bool)((1 << bit) & x));
    G[path].prefixCnt++;
  }
  G[path].valueCnt++;
}

int prefixOperation(int x) {
  string path = "";
  for (int bit = BIT_MAX; bit >= 0; bit--) {
    int branch;
    if (G[path + '1'].prefixCnt == 0)
      branch = 0;
    else if (G[path + '0'].prefixCnt == 0)
      branch = 1;
    else
      branch = 1 - (bool)((1 << bit) & x);
    path += ('0' + branch);
  }
  int ans = 0;
  for (int i = 0; i < (int)path.size(); i++)
    ans = ans * 2 + path[i] - '0';
  return ans;
}

int main(){
  fin >> n;
  for (int i = 1; i <= n; i++) {
    int x;
    fin >> x;
    v[i] = (v[i - 1] ^ x);
  }

  int mx = -1, le = -1, ri = -1;
  insertOperation(0);
  pos[0] = 0;
  for (int i = 1; i <= n; i++) {
    int x = prefixOperation(v[i]);
    if (mx < (x ^ v[i])) {
      mx = (x ^ v[i]);
      le = pos[x];
      ri = i;
    }
    insertOperation(v[i]);
    pos[v[i]] = i;
  }
  le++;

  fout << mx << " " << le << " " << ri << "\n";
  return 0;
}