Cod sursa(job #2904880)

Utilizator MarcGrecMarc Grec MarcGrec Data 18 mai 2022 12:57:55
Problema Xor Max Scor 70
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.47 kb
#define MAX_N 100000
#define MAX_BIT 20

#include <fstream>
using namespace std;

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

class tree
{
private:
	struct node
	{
		node* next[2] = { nullptr, nullptr };
		int index;
	} *root = new node;
	
	void __cleanup(const node* _node)
	{
		if (_node != nullptr)
		{
			__cleanup(_node->next[0]);
			__cleanup(_node->next[1]);
			delete _node;
		}
	}
	
public:
	~tree()
	{
		__cleanup(root);
	}
	
	void add(const int value, const int index)
	{
		node* _node = root;
		for (int i = MAX_BIT; i >= 0; --i)
		{
			const int child = (value >> i) & 1;
			if (_node->next[child] == nullptr)
				_node->next[child] = new node;
			_node = _node->next[child];
		}
		_node->index = index;
	}
	
	void retrieve(const int value, int& out_value, int& index)
	{
		node* _node = root;
		out_value = 0;
		for (int i = MAX_BIT; i >= 0; --i)
		{
			int child = ((value >> i) & 1) ^ 1;
			if (_node->next[child] == nullptr)
				child ^= 1;
			out_value |= child << i;
			_node = _node->next[child];
		}
		index = _node->index;
	}
} T;

int n, v_max = -1, i_max, j_max;

int main()
{
	fin >> n;
	for (int v, i, j = 1, xp = 0, x; j <= n; ++j)
	{
		fin >> x;
		T.add(xp, j);
		xp ^= x;
		T.retrieve(xp, v, i);
		v ^= xp;
		if (v > v_max)
		{
			v_max = v;
			i_max = i;
			j_max = j;
		}
	}
	fout << v_max << ' ' << i_max << ' ' << j_max;
    fin.close();
    fout.close();
    return 0;
}