Cod sursa(job #2070783)

Utilizator Kzsolty96SAPIENTIA OSZTIAN DANIEL KUCSVAN Kzsolty96 Data 19 noiembrie 2017 21:59:13
Problema Xor Max Scor 25
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.67 kb
#include<fstream>
#include<climits>


using namespace std;

#define MAX_SIZE 21

int max(int a, int b) {
	return a < b ? b : a;
}

struct Trie
{
	int value = 0; 
	int end_index = 0;
	Trie *arr[2] = { 0 };
};

bool nth_bit(int x, int n) {
	return x & (1 << n);
}


void insert(Trie *root, int pre_xor, int end_index)
{
	Trie *temp = root;

	for (int i = MAX_SIZE - 1; i >= 0; i--)
	{
		bool val = nth_bit(pre_xor, i);

		if (nullptr == temp->arr[val])
			temp->arr[val] = new Trie;

		temp = temp->arr[val];
	}

	temp->end_index = end_index;
	temp->value = pre_xor;
}

int query(Trie *root, int pre_xor, int& end_index)
{
	Trie *temp = root;
	for (int i = MAX_SIZE - 1; i >= 0; i--)
	{
		bool val = nth_bit(pre_xor, i);

		if (nullptr != temp->arr[1 - val])
			temp = temp->arr[1 - val];

		else {
			temp = temp->arr[val];
		}
	}

	end_index = temp->end_index;
	return pre_xor ^ (temp->value);
}


int main()
{
	ifstream f("xormax.in");
	ofstream g("xormax.out");

	Trie *root = new Trie;
	int n, x;
	insert(root, 0, 0);

	int result = INT_MIN, pre_xor = 0;
	int start_index = 1, end_index = 1;

	f >> n;

	for (int i = 0; i<n; i++)
	{
		f >> x;

		pre_xor = pre_xor^x;

		insert(root, pre_xor, i + 1);

		int start_i, end_i;
		int tmpResult = query(root, pre_xor, end_i);
		if (result < tmpResult) {
			start_index = end_i + 1;
			end_index = i + 1;
			result = tmpResult;
		}
		if (result == tmpResult) {
			if (end_index - start_index > i - end_i) {
				start_index = end_i + 1;
				end_index = i + 1;
				result = tmpResult;
			}
		}

	}
	g << result << " " << start_index << " " << end_index << "\n";
}