Cod sursa(job #2662036)

Utilizator Iulia25Hosu Iulia Iulia25 Data 23 octombrie 2020 12:40:12
Problema Xor Max Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.25 kb
#include <fstream>
//#include <iostream>

using namespace std;

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


const int NR = 8e6, N = 1e5 + 5;

int numar[NR], nr[NR];
int v[N];
int Max = -1, pozi, pozj, n;

void adaug(int x, int K)  {
  int aux[25];
  aux[0] = 0;
  for (int i = 21; i; --i, x >>= 1)
    aux[i] = x & 1;
  int poz = 1;
  ++nr[poz];
  for (int i = 1; i <= 21; ++i)  {
    poz = poz + poz + aux[i];
    ++nr[poz];
  }
  numar[poz] = K;
}

pair <int, int> Query(int x)  {
  int aux[25];
  aux[0] = 0;
  for (int i = 21; i; --i, x >>= 1)
    aux[i] = (x & 1) ^ 1;

  int poz = 1, ans = 0;
  for (int i = 1; i <= 21; ++i)  {
    if (nr[poz + poz + aux[i]])  {
      ans = (ans << 1) + 1;
      poz = poz + poz + aux[i];
    }
    else  {
      ans <<= 1;
      poz = poz + poz + (aux[i] ^ 1);
    }
  }
  return {numar[poz], ans};
}

int main()  {
  fin >> n;
  for (int i = 1; i <= n; ++i)  {
    fin >> v[i];
    v[i] ^= v[i - 1];
    adaug(v[i], i);
    pair <int, int> aux = Query(v[i]);
    if (v[i] > aux.second)  {
      aux.second = v[i];
      aux.first = 0;
    }
    if (aux.second > Max)  {
      Max = aux.second;
      pozi = aux.first;
      pozj = i;
    }
  }
  fout << Max << ' ' << min(pozi + 1, pozj) << ' ' << pozj;
  return 0;
}