Cod sursa(job #2909612)

Utilizator lolismekAlex Jerpelea lolismek Data 14 iunie 2022 12:00:13
Problema Xor Max Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.13 kb
#include <iostream>
#include <fstream>
#include <cmath>

#define pii pair <int, int>

using namespace std;

ofstream fout("xormax.out");

class InParser {
private:
	FILE *fin;
	char *buff;
	int sp;
 
	char read_ch() {
		++sp;
		if (sp == 4096) {
			sp = 0;
			fread(buff, 1, 4096, fin);
		}
		return buff[sp];
	}
 
public:
	InParser(const char* nume) {
		fin = fopen(nume, "r");
		buff = new char[4096]();
		sp = 4095;
	}
	
	InParser& operator >> (int &n) {
		char c;
		while (!isdigit(c = read_ch()) && c != '-');
		int sgn = 1;
		if (c == '-') {
			n = 0;
			sgn = -1;
		} else {
			n = c - '0';
		}
		while (isdigit(c = read_ch())) {
			n = 10 * n + c - '0';
		}
		n *= sgn;
		return *this;
	}
	
	InParser& operator >> (long long &n) {
		char c;
		n = 0;
		while (!isdigit(c = read_ch()) && c != '-');
		long long sgn = 1;
		if (c == '-') {
			n = 0;
			sgn = -1;
		} else {
			n = c - '0';
		}
		while (isdigit(c = read_ch())) {
			n = 10 * n + c - '0';
		}
		n *= sgn;
		return *this;
	}
};

const int SIGMA = 2, P = 21;

struct trie{
	int poz;
	trie *nxt[SIGMA];
};

trie root;

void insertTrie(trie *nod, int val, int bit, int i){
	if(bit < 0){
		nod -> poz = i;
		return;
	}

	int ind = (val & (1 << bit)) != 0;
	if(nod -> nxt[ind] == NULL)
		nod -> nxt[ind] = new trie();


	insertTrie(nod -> nxt[ind], val, bit - 1, i);
}

pii findTrie(trie *nod, int val, int bit, int ans){
 	if(bit < 0)
 		return {ans, nod -> poz};
 	
 	int ind = (val & (1 << bit)) != 0;

 	ind = !ind;

 	if(nod -> nxt[ind] == NULL)
 		ind = !ind;

 	return findTrie(nod -> nxt[ind], val, bit - 1, ans + ind * (1 << bit));
}

int main(){

	InParser fin("xormax.in");

	int n, Xsum = 0, maxi = -1;
	fin >> n;
	insertTrie(&root, 0, P, 0);

	int l = 0, r = 0;

	for(int i = 1; i <= n; i++){
		int x;
		fin >> x;
		Xsum ^= x;

		pii tmp = findTrie(&root, Xsum, P, 0);

		if((tmp.first ^ Xsum) > maxi){
			maxi = (tmp.first ^ Xsum);
			l = tmp.second + 1;
			r = i;
		}

		insertTrie(&root, Xsum, P, i);
	}

	fout << maxi << ' ' << l << ' ' << r << '\n';

	return 0;
}