Cod sursa(job #1478172)

Utilizator theprdvtheprdv theprdv Data 28 august 2015 02:10:13
Problema Xor Max Scor 90
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.85 kb
#define _CRT_SECURE_NO_DEPRECATE
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <assert.h>

#define DIM (1 << 13)
#define MAXN 100000
#define in (MyStream.r_int())
#define bit ((x >> i) & 1)
#define MAX(x, y) ( ((x) > (y)) ? (x) : (y) )

using namespace std;

class Stream{
private:
	int pos = DIM, len;
	char buf[DIM];

public:
	inline int r_int(){  // read int
		while (buf[pos] < '0' || buf[pos] > '9')
			if (pos++ == DIM) len = (int)fread(buf, 1, DIM, stdin), pos = 0;

		int val = 0;
		while (buf[pos] >= '0' && buf[pos] <= '9'){
			if (pos == len) break;
			val = val * 10 + buf[pos] - '0';
			if (++pos == DIM) len = (int)fread(buf, 1, DIM, stdin), pos = 0;
		}
		return val;
	}

	inline void w_int(int k, char end){  // write int
		char lim[16], *s;
		s = lim + 15; *s = 0;
		*--s = end;

		do{
			--s;
			*s = k % 10 + '0';
			k /= 10;
		} while (k);
		fputs(s, stdout);
	}
};

struct Trie{
	int pos;
	Trie *son[2];

	Trie(){
		son[0] = son[1] = 0;
	}
} *T = new Trie;

void insert(int x, int i){
	Trie *node = T;

	for (int i = 20; i >= 0; --i){
		if (!node->son[bit]) node->son[bit] = new Trie;
		node = node->son[bit];
	}
	node->pos = i;
}

int pos;

int xormax(int x){
	Trie *node = T;
	int ret = 0;

	for (int i = 20; i >= 0; --i){
		if (node->son[!bit])
			node = node->son[!bit],
			ret += 1 << i;
		else node = node->son[bit];
	}
	pos = node->pos;
	return MAX(ret, x);
}

int main(){
	assert(freopen("xormax.in", "r", stdin));
	assert(freopen("xormax.out", "w", stdout));

	int max = -1, x = 0, N, y, l, r;
	Stream MyStream;
	N = in;

	for (int i = 0; i < N; ++i){
		x ^= in;
		insert(x, i);
		y = xormax(x);
		if (y > max) max = y, l = pos + 1, r = i + 1;
	}

	MyStream.w_int(max, ' ');
	MyStream.w_int(l + 1, ' ');
	MyStream.w_int(r, '\n');

	return 0;
}