Cod sursa(job #48763)

Utilizator eferLiviu Ciortea efer Data 5 aprilie 2007 01:08:47
Problema Xor Max Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.96 kb
#include <cstdio>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cassert>
#include <cmath>
#include <algorithm>
#include <vector>
#include <set>
#include <map>
#include <list>
#include <queue>
#include <utility>
#include <string>
using namespace std;

#define REP(i, N) for (int i = 0; i < (N); ++i)
#define REPV(i, a, b) for (int i = (a); i <= (b); ++i)
#define REPD(i, N) for (int i = (N)-1; i >= 0; --i)
#define REPVD(i, b, a) for (int i = (b); i >= (a); --i)
#define REPIT(it, v) for (it = (v).begin(); it != (v).end(); ++it)
#define SZ(a) ((int)(a).size())
#define MP make_pair
#define PB push_back
#define X first
#define Y second
#define ALL(a) (a).begin(), (a).end()
#define CLR(a) memset((a), 0, sizeof(a))
#define MSET(a, v) memset((a), v, sizeof(a))
#define CPY(dest, source) memcpy(dest, source, sizeof(dest))

typedef long long LL;
typedef vector<int> VI;
typedef vector<string> VS;
typedef pair<int, int> PII;
typedef set<int> SI;
typedef map<int, int> MII;
typedef deque<int> QI;
typedef deque<PII> QPII;

const int MAXN = 102400;
const int MAXB = 21;
int have[4<<MAXB], sum[MAXN];

void put(int x) {
	int n = 0;
	REPD(b, MAXB) {
		have[n] = 1;
		if (x & (1 << b)) n = (n+1) << 1;
		else n = (n << 1) | 1;
	}
}

int main() {
	freopen("xormax.in", "rt", stdin);
	freopen("xormax.out", "wt", stdout);

	put(0);
	sum[0] = 0;

	int N;
	scanf("%d", &N);
	REPV(i, 1, N) {
		int x;
		scanf("%d", &x);
		sum[i] = sum[i-1] ^ x;
		put(sum[i]);
	}

	int res = 0, u, v;
	REPV(i, 1, N) {
		int x = sum[i], y = 0, n = 0;

		REPD(b, MAXB) {
			int nn[2], c = (x & (1 << b)) != 0;
			nn[0] = (n << 1) | 1, nn[1] = (n+1) << 1;
			if (have[nn[!c]]) c = !c;
			n = nn[c];
			if (c) y |= 1 << b;
		}

		if ((x ^ y) > res) {
			res = x ^ y;
			u = i;
			v = y;
		}
	}

	REP(i, N+1) if (sum[i] == v) {
		v = i;
		break;
	}

	if (u > v) swap(u, v);

	printf("%d %d %d\n", res, u+1, v);

	return 0;
}