Cod sursa(job #915267)

Utilizator vladtarniceruVlad Tarniceru vladtarniceru Data 14 martie 2013 21:22:24
Problema Xor Max Scor 90
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.44 kb
#include <algorithm>
#include <iostream>
#include <fstream>
#include <cstring>
using namespace std;

#define forv(i, v) for(size_t i = 0; i < (v).size(); i++)
#define forit(it, v) for(typeof((v).begin()) it = (v).begin(); it != (v).end(); it++)
#define mp make_pair
#define pb push_back
#define pf push_front
#define all(v) v.begin(), v.end()

typedef long double lod;
typedef long long lol;
typedef pair<int, int> pii;

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

struct myt
{
	int id;
	myt *next[2];
	myt()
	{
		memset(this->next, 0, sizeof(this->next)); this->id = 0;
	}
};

myt *root = new myt;
int n, rd, bt, sum, sol = -1;
int s, f, iii;
int add_num, sol_num;

inline void add(myt *root, int bit)
{
	if (bit == -1)
	{
		root->id = max(root->id, iii);
		return ;
	}
	bt = ((add_num & (1 << bit)) > 0 ? 1 : 0);
	if (root->next[bt] == 0)
		root->next[bt] = new myt;
	add(root->next[bt], bit - 1);
}

inline int take(myt *root, int bit)
{
	if (bit == -1) return root->id;
	bt = ((add_num & (1 << bit)) > 0 ? 0 : 1);
	if (!(root->next[bt] == 0))
		sol_num |= (1 << bit);
	else bt = !bt;
	return take(root->next[bt], bit - 1);
}

int main()
{
	fin >> n;
	add(root, 21);
	for (iii = 1; iii <= n; iii++)
	{
		fin >> rd;
		sum = sum ^ rd;
		add_num = sum; sol_num = 0;
		add(root, 21);
		int var = take(root, 21);
		if (sol < sol_num)
		{
			sol = sol_num;
			s = var;
			f = iii;
		}
	}
	
	fout << sol << ' ' << s + 1 << ' ' << f; fout.close();
	return 0;
}