Cod sursa(job #2971876)

Utilizator matwudemagogul matwu Data 28 ianuarie 2023 11:12:49
Problema Xor Max Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.6 kb
#include <bits/stdc++.h>
using namespace std;
ifstream fin("xormax.in");
ofstream fout("xormax.out");
const int N = 1e5 + 1;
int n, lgmax, l, r;
long long ans;
vector<int> v(N);
vector<long long> x(N);
vector<vector<int>> trie(1, vector<int>(2, -1));
vector<int> pos(N * 30 + 1);
int main(){
	
	fin >> n;
	for(int i = 1; i <= n; i++){
		fin >> v[i];
		x[i] = x[i - 1] ^ v[i];
		lgmax = max(lgmax, (int)log2(x[i]) + 1);
	}
	bitset<30> b(x[1]);
	int curr = 0;
	for(int i = lgmax - 1; i >= 0; i--){
		if(trie[curr][b[i]] == -1){
			trie[curr][b[i]] = trie.size();
			trie.push_back(vector<int>(2, -1));
		}
		curr = trie[curr][b[i]];
	}	
	pos[curr] = 1;
	for(int i = 2; i <= n; i++){
		
		bitset<30> b(x[i]);
		int curr = 0;
		for(int j = lgmax - 1; j >= 0; j--){
			if(b[j] == 0){
				if(trie[curr][1] != -1){
					curr = trie[curr][1];
				}
				else if(trie[curr][0] != -1){
					curr = trie[curr][0];
				}			
			}else{
				if(trie[curr][0] != -1){
					curr = trie[curr][0];
				}else if(trie[curr][1] != -1){
					curr = trie[curr][1];
				}			
			}
		}
		ans = max(ans, x[i] ^ x[pos[curr]]);
		if(ans < x[i] ^ x[pos[curr]]){
			ans = x[i] ^ x[pos[curr]];
			l = pos[curr] + 1;
			r = i;
		}
		else if(ans == x[i] ^ x[pos[curr]]){
			if(l > pos[curr] + 1){
				l = pos[curr] + 1;
			}
		}
		curr = 0;
		for(int j = lgmax - 1; j >= 0; j--){
			if(trie[curr][b[j]] == -1){
				trie[curr][b[j]] = trie.size();
				trie.push_back(vector<int>(2, -1));
			}
			curr = trie[curr][b[j]];
		}
		if(pos[curr] == 0) pos[curr] = i;
	}

	fout << ans << " " << l << " " << r;
}