Cod sursa(job #2909613)

Utilizator andrei_C1Andrei Chertes andrei_C1 Data 14 iunie 2022 12:02:10
Problema Xor Max Scor 85
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.61 kb
#include <bits/stdc++.h>
#pragma GCC optimize("Ofast")

using namespace std;

ifstream fin("xormax.in");
ofstream fout("xormax.out");

const int SIGMA = 2;
const int DEPTH = 20;
const int INF = 1e9;
const int VMAX = (1 << 21) - 1;

int N;
int xuma, xuma0;
int maxi, start, stop;

struct Node {
	int pos;
	Node* children[SIGMA];

	// Node () {
	// 	pos = 0;

	// 	for(int i = 0; i < SIGMA; i++) {
	// 		children[i] = nullptr;
	// 	}
	// }
};

Node root;

void Insert(Node *root, const int &value, const int &pos, int index) {
	if(index >= 0) {
		bool x = (value & (1 << index)) != 0;

		if(root->children[x] == nullptr) {
			root->children[x] = new Node ();
		}

		Insert(root->children[x], value, pos, index - 1);
	} else {
		root->pos = pos;
	}
}

void Insert(const int &value, const int &pos) {
	Insert(&root, value, pos, DEPTH);
}

pair<int, int> Prefix(Node *root, const int &value, const int &index, int answer = 0) {
	if(index >= 0) {
		bool x = (value & (1 << index)) != 0;

		if(root->children[x] == nullptr) {
			x ^= 1;
		}

		return Prefix(root->children[x], value, index - 1, answer + x * (1 << index));
	} else {
		return {answer, root->pos};
	}
}

pair<int, int> Prefix(const int &value) {
	return Prefix(&root, value, DEPTH);
}

int main () {
	fin >> N;

	maxi = -INF;
	Insert(0, 0);

	for(int i = 1; i <= N; i++) {
		int x;
		fin >> x;

		xuma ^= x; // hahaha ce amuzat, te-ai prins?
		pair<int, int> p = Prefix(xuma ^ VMAX);

		xuma0 = p.first;

		if((xuma ^ xuma0) > maxi) {
			maxi = (xuma ^ xuma0);
			stop = i;
			start = p.second + 1;
		}

		Insert(xuma, i);
	}

	fout << maxi << " " << start << " " << stop << '\n';
	return 0;
}