Cod sursa(job #3127673)

Utilizator cezar_titianuTitianu Cezar cezar_titianu Data 7 mai 2023 18:08:44
Problema Xor Max Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.45 kb
#include <fstream>
#include <vector>

using namespace std;

const int MAX_SIZE = 21 * 100000 + 5;

struct node {
	int chd[2] = { -1, -1 };
	int id = -1;
};

vector <node> trie(1);

void CreateNode(int nod, bool type) {
	if (trie[nod].chd[type] == -1) {
		trie[nod].chd[type] = trie.size();
		trie.emplace_back();
	}
}

void Add(int nod, int num, int bit, int id) {
	if (bit < 0) {
		trie[nod].id = id;
		return;
	}
	int val = 0;
	if ( num & ( 1 << bit ) ) {
		val = 1;
	}
	CreateNode( nod, val );
	Add(trie[nod].chd[val], num, bit - 1, id);
}

std::pair <int, int> FindOpp(int nod, int num, int bit) {
	if (bit < 0) {
		return { trie[nod].id, 0 };
	}
	int val = 0;
	if ( num & ( 1 << bit ) ) {
		val = 1;
	}
	if (trie[nod].chd[val ^ 1] != -1) {
		std::pair <int, int> sol;
		sol = FindOpp(trie[nod].chd[val ^ 1], num, bit - 1);
		sol.second |= 1 << bit;
		return sol;
	}
	else {
		std::pair <int, int> sol;
		sol = FindOpp(trie[nod].chd[val], num, bit - 1);
		return sol;
	}
}

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

    int n, i, x, val = 0;
	int pos1, pos2, max_sol = -1;
	std::pair <int, int> new_sol;
	
    fin >> n;

	Add ( 0, 0, 20, 0 );
	
    for ( i = 1; i <= n; i++ ) {
        fin >> x;
        val = val ^ x;
		new_sol = FindOpp ( 0, val, 20 );
		if ( new_sol.second > max_sol ) {
			max_sol = new_sol.second;
			pos1 = new_sol.first + 1;
			pos2 = i;
		}
		Add ( 0, val, 20, i );
    }

    fout << max_sol << " " << pos1 << " " << pos2;
}