Cod sursa(job #2661181)

Utilizator Iulia25Hosu Iulia Iulia25 Data 21 octombrie 2020 15:57:39
Problema Xor Max Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.14 kb
#include <fstream>

using namespace std;

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

int n;
int nr[3145730];
int numar[3145730];
int v[100005];

pair <int, int> Max;

void adaug(int x, int K)  {
	int aux[25], nraux = 0;
	while (x) {
		aux[++nraux] = x & 1;
		x >>= 1;
	}
	while (nraux < 22)
		aux[++nraux] = 0;

	int poz = 1;
	for (int i = nraux; i; --i)  {
		++nr[poz];
		poz = poz + poz + aux[i];
	}
  numar[poz / 2] = K;
}

pair <int, int> query(int x)  {
	int aux[25], nraux = 0;
	while (x) {
		aux[++nraux] = x & 1;
		x >>= 1;
	}
	while (nraux < 22)
		aux[++nraux] = 0;

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

int main()  {
	fin >> n;
	int J = 0;
	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]);
		aux = max(aux, {v[i], 0});
		if (aux.first > Max.first)
      Max = aux, J = i;
	}
	fout << Max.first << ' ' << Max.second + 1 << ' ' << J;
  return 0;
}