Cod sursa(job #1302927)

Utilizator tamionvTamio Vesa Nakajima tamionv Data 27 decembrie 2014 14:37:19
Problema Xor Max Scor 10
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.41 kb
#include <fstream>
using std::ifstream;
using std::ofstream;

#include <vector>
using std::vector;

#include <numeric>
using std::partial_sum;

template <typename T>
struct rezultat{
	int start, finish;
	T val; };

template <typename T, typename Op, typename RevOp>
class smenul_lui_Mars{
	vector<T> interior;
public:
	smenul_lui_Mars(const vector<T> v):
		interior(v.size()+1, 1 << 30){
		partial_sum(v.begin(), v.end(), interior.begin() + 1, Op()); }
	T query(const int a, const int b){
		return RevOp()(interior[b], interior[a]); } };

template <typename T>
struct bit_xor{
	T operator()(const T& lhs, const T& rhs){
		return (lhs == (1 << 30)) ? rhs : (rhs == (1 << 30)) ? lhs : lhs ^ rhs; } };

template <typename T, typename Op, typename RevOp>
rezultat<T> find_subsir_max(const vector<T>& v){
	smenul_lui_Mars<T, Op, RevOp> s(v);
	rezultat<T> r;
	r.start = 0;
	r.finish = 0;
	r.val = 0;
	for(int i = 0; i <= v.size(); ++i){
		for(int j = i+1; j <= v.size(); ++j){
			const T v = s.query(i, j);
			if(r.val <= v){
				r.val = v;
				r.start = i+1;
				r.finish = j; } } }
	return r; }

int main(){
	ifstream f("xormax.in");
	int n = 0;
	f >> n;
	vector<unsigned int> nr(n, 0);
	for(int i = 0; i < n; ++i){
		f >> nr[i]; }
	const rezultat<unsigned int>& rez = find_subsir_max<unsigned int, bit_xor<unsigned int>, bit_xor<unsigned int> >(nr);
	ofstream g("xormax.out");
	g << rez.val << " " << rez.start << " " << rez.finish;
	return 0; }