Cod sursa(job #3335265)

Utilizator StefanIancuTempStefan Iancu StefanIancuTemp Data 22 ianuarie 2026 09:47:20
Problema Xor Max Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.55 kb
#include <iostream>
#include <fstream>

using namespace std;

const int NB = 21;

struct nod {
	int lastPos;
	nod* fiu0, * fiu1;
};

nod* adauga(nod* r, int val, int pos, int nb) {
	if (r == NULL) {
		r = new nod;
		r -> fiu0 = r -> fiu1 = NULL;
	}
	nb--;
	if (nb == -1) {
		r->lastPos = pos;
		return r;
	}
	if ((val & (1 << nb)) == 0) {
		r->fiu0 = adauga(r->fiu0, val, pos, nb);
	}
	else {
		r->fiu1 = adauga(r->fiu1, val, pos, nb);
	}
	return r;
}
void interogare(nod* root, int val, int& sMax, int& posMax, int nb) {
	if (nb == 0) {
		sMax = 0;
		posMax = root->lastPos;
		return;
	}
	nb--;
	int p2 = ((1 << nb) & val);
	if (p2 == 0) {
		if (root->fiu1 != NULL) {
			interogare(root -> fiu1, val, sMax, posMax, nb);
			sMax += (1 << nb);
		}
		else {
			interogare(root->fiu0, val, sMax, posMax, nb);
		}
	}
	else {
		if (root->fiu0 != NULL) {
			interogare(root->fiu0, val, sMax, posMax, nb);
			sMax += (1 << nb);
		}
		else {
			interogare(root->fiu1, val, sMax, posMax, nb);
		}
	}
}

int main()
{
	ifstream fin("xormax.in");
	ofstream fout("xormax.out");
	int n;
	fin >> n;
	nod* root = adauga(NULL, 0, 0, NB);
	int prefix = 0, sMax = -1, st = -1, dr = -1;
	for (int i = 1; i <= n; i++) {
		int xi;
		fin >> xi;
		prefix ^= xi;
		int sMaxI;
		int posMaxI;
		interogare(root, prefix, sMaxI, posMaxI, NB);
		if (sMaxI > sMax) {
			sMax = sMaxI;
			st = posMaxI + 1;
			dr = i;
		}
		root = adauga(root, prefix, i, NB);
	}
	fout << sMax << " " << st << " " << dr << "\n";
	fin.close();
	fout.close();
}