Cod sursa(job #3317800)

Utilizator Cezar2009Cezar Mihai Titihazan Cezar2009 Data 25 octombrie 2025 13:25:37
Problema Xor Max Scor 60
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 3.7 kb
//https://infoarena.ro/problema/xormax

#pragma GCC optimize ("Ofast")
#pragma GCC optimize ("fast-math")
#pragma GCC optimize ("unroll-loops")
#define _USE_MATH_DEFINES

#include <iostream>
#include <fstream>
//#include <vector>
#include <cstring>
//#include <cmath>
//#include <bitset>
//#include <queue>
//#include <stack>
//#include <utility>
#include <algorithm>
//#include <string>
//#include <map>
//#include <unordered_map>
//#include <set>
//#include <unordered_set>
//#include <cstdint>
//#include <climits>
//#include <iomanip>
//#include <cstdio>
//#include <tuple>

using namespace std;

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

const int NRMAX = 100000;
const int NRCIF = 30;
int v[NRMAX + 5];

struct Nod
{
	int nrc, nrcd, ind;

	Nod* ch[2];

	Nod() : nrc{ 0 }, nrcd{ 0 }, ind{ 0 }, ch {} {};
};

void backtr_insert(Nod* nod, char* c, int ind)
{
	nod->nrcd += 1;

	if (*c != '\0')
	{
		int nr = *c - '0';

		if (!nod->ch[nr])
			nod->ch[nr] = new Nod();

		//cout << nr << " " << nod->nrc << " " << nod->nrcd << "\n";

		backtr_insert(nod->ch[nr], c + 1, ind);
	}
	else
	{
		nod->nrc += 1;
		nod->ind = ind;
	}
}

int backtr_rezolvare(Nod* nod, char* c)
{
	//cout << *c << "c ";
	if (*c != '\0')
	{
		int nr = *c - '0';
		int invnr = nr ^ 1;

		//cout << nr << " " << nod->nrc << " " << nod->nrcd << " " << nod->ind << "\n";

		if (nod->ch[invnr])
			return backtr_rezolvare(nod->ch[invnr], c + 1);
		else
			return backtr_rezolvare(nod->ch[nr], c + 1);
	}
	else
	{
		return nod->ind;
	}
}

void insert(Nod* nod, int x, int ind)
{
	int j, masca;
	char ch[NRCIF + 5];
	memset(ch, 0, sizeof ch);

	j = 1;
	if (x == 0)
	{
		ch[1] = '0';
		++j;
	}
	else
	{
		for (masca = 1; masca < (1 << NRCIF); masca <<= 1, ++j)
		{
			if (x & masca)
				ch[j] = '1';
			else
				ch[j] = '0';
		}
		reverse(ch + 1, ch + j);
	}
	--j;

	//for(int it = 1; it <= j; ++it)
	//    cout<<ch[it]<<" "; 

	backtr_insert(nod, ch + 1, ind);
}

int rezolvare(Nod* nod, int x)
{
	int j, masca;
	char ch[NRCIF + 5];
	memset(ch, 0, sizeof ch);

	j = 1;
	if (x == 0)
	{
		ch[1] = '0';
		++j;
	}
	else
	{
		for (masca = 1; masca < (1 << NRCIF); masca <<= 1, ++j)
		{
			if (x & masca)
				ch[j] = '1';
			else
				ch[j] = '0';
		}
		reverse(ch + 1, ch + j);
	}
	--j;

	//for(int it = 1; it <= j; ++it)
	//    cout<<ch[it]<<" "; 
	//cout << "\n";

	return backtr_rezolvare(nod, ch + 1);
}

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);

	Nod* rad = new Nod();
	int n, x, ix, i;
	int rez, st = 1, dr = 1;

	insert(rad, 0, 0);

	fin >> n;
	for (i = 1; i <= n; ++i)
	{
		fin >> x;
		if (i == 1)
			ix = x;
		else
			ix ^= x;
		//cout << ix << " ";
		v[i] = ix;
		insert(rad, ix, i); // trebuie si pozitia (i)

		if (i == 1)
		{
			rez = ix;
			continue;
		}

		int nr = rezolvare(rad, ix);
		//cout << nr << " ";
		if (nr)
		{
			if ((v[i] ^ v[nr]) > rez)
			{
				rez = v[i] ^ v[nr];
				st = nr + 1;
				dr = i;
			}
		}
		//cout << "\n";
	}

	fout << rez << " " << st << " " << dr;

	return 0;
}

// Facem xor intre toate numerele pe rand.
// La fiecare adaugam in trie, pe biti numarul. Trebuie sa facem si un vector ce contine fiecare nod
// Dupa aceia trebuie sa gasim un numar j<i a.i. xorul sa fie maxim (atunci cand exista pt fiecare 0 un 1 si pt fiecare 1 un 0, alfel punem ce e).


// insert ()
// scriu numarul in binar


// luam numerele pe rand numerele
// xi^=x;
// v[i]=xi;
// insert(xi)
// rezolvare(xi)
// daca am gasit un numar astfel incat sa se respecte cerintele vedem daca v[i]^v[j] > rez
// rez=v[i]^v[j]; st=j+1; dr=i;

// fout