Cod sursa(job #882437)

Utilizator howsiweiHow Si Wei howsiwei Data 19 februarie 2013 08:59:38
Problema Xor Max Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.22 kb
#include <iostream>
#include <fstream>
#include <algorithm>
#include <vector>
#include <bitset>
#include <cassert>
using namespace std;
typedef pair<int,int> ii;
bitset<1<<22> in;
vector<int> mini(1<<21,-1);//min i st a1^a2^...^ai=index
pair<int,ii> best(0,ii(0,1));

void insert(int xorsum, int i) {
	mini[xorsum^1<<21]=i;
	while (!in.test(xorsum)) {
		in.set(xorsum);
		xorsum>>=1;
	}
}

void findbest(int xorsum, int i) {
	int maxxor=1;
	for (int j=20; j>=0; --j) {
		maxxor<<=1;
		if (!(1<<j & xorsum)) maxxor^=1;
		if (!in.test(maxxor)) maxxor^=1;
	}
	if (best.first < (maxxor^xorsum)) {
		//cout << maxxor << ' ' << xorsum << '\n';
		best.first = (maxxor^xorsum);
		best.second.first=min(i,mini[maxxor^1<<21]);
		best.second.second=max(i,mini[maxxor^1<<21]);
	}
	//assert(maxxor&(1<<21) && xorsum&(1<<21));
	//assert(best.first<(1<<21));
}

int main() {
	ifstream fin("xormax.in");
	ofstream fout("xormax.out");
	int n; fin >> n;
	int xorsum[n+1];
	xorsum[0]=1<<21;
	in.set(1);
	insert(xorsum[0],0);
	for (int i=1, temp; i<=n; ++i) {
		fin >> temp;
		xorsum[i]=xorsum[i-1]^temp;
		findbest(xorsum[i],i);
		insert(xorsum[i],i);
	}
	fout << best.first << ' ' << best.second.first+1 << ' ' << best.second.second;
	//cout << in.count();
	return 0;
}