Pagini recente » Cod sursa (job #653407) | Cod sursa (job #832653) | Cod sursa (job #328445) | Cod sursa (job #1048680) | Cod sursa (job #3354029)
#include<iostream>
#include<vector>
#include<string>
#include<fstream>
using namespace std;
ifstream fin("xormax.in");
ofstream fout("xormax.out");
struct Node{
char value;
vector<int> children_index;
int final;
};
string change_to_bitwise(int number){
string return_string = "";
while(number){
if(number % 2 == 1){
return_string += '1';
}
else{
return_string += '0';
}
number /= 2;
}
return return_string;
}
//elementul de pe pozitia 0 este root
void createTrie(const string& chain, vector<Node>& return_vector){
int parent_index = 0;
for(int j = chain.size() - 1; j >= 0; j--){
if(!return_vector[parent_index].children_index.empty()){
if(return_vector[return_vector[parent_index].children_index[0]].value == chain[j]){
parent_index = return_vector[parent_index].children_index[0];
}
else {
if(return_vector[parent_index].children_index.size() == 1){
return_vector.push_back({chain[j], {}, 0});
return_vector[parent_index].children_index.push_back(return_vector.size() - 1);
parent_index = return_vector.size() - 1;
}
else{
parent_index = return_vector[parent_index].children_index[1];
}
}
}
else{
return_vector.push_back({chain[j], {}, 0});
return_vector[parent_index].children_index.push_back(return_vector.size() - 1);
parent_index = return_vector.size() - 1;
}
if(j == 0){
return_vector[parent_index].final++;
}
}
}
int findMaxXOR(const string& chain, vector<Node>& return_vector){
int parent_index = 0;
int optimal_xor = 0;
for (int j = 20; j >= 0; j--){
char bit_curent = chain[j];
char bit_dorit = (bit_curent == '1' ? '0' : '1');
int next_node = -1;
for (int child_idx : return_vector[parent_index].children_index){
if (return_vector[child_idx].value == bit_dorit){
next_node = child_idx;
break;
}
}
if (next_node != -1){
optimal_xor += (1 << j);
parent_index = next_node;
}
else{
if (!return_vector[parent_index].children_index.empty()){
parent_index = return_vector[parent_index].children_index[0];
}
}
}
return optimal_xor;
}
int main(){
int n;
fin >> n;
vector<int> v(n);
for(int i = 0; i < n; i++){
fin >> v[i];
}
vector<int> values_xor(n);
values_xor[0] = v[0];
for(int i = 1; i < n; i++){
values_xor[i] = values_xor[i - 1] ^ v[i];
}
vector<string> chains;
for(int i = 0; i < n; i++){
string s = change_to_bitwise(values_xor[i]);
while(s.size() < 21){
s += '0';
}
chains.push_back(s);
}
vector<Node> return_vector;
return_vector.push_back({'R', {} , 0});
string zero_chain = change_to_bitwise(0);
while(zero_chain.size() < 21){
zero_chain += '0';
}
createTrie(zero_chain, return_vector);
int max_overall = 0, ok_idx = -1;
for(int i = 0; i < chains.size(); i++){
int current_max = findMaxXOR(chains[i], return_vector);
if(current_max > max_overall){
max_overall = current_max;
ok_idx = i;
}
createTrie(chains[i], return_vector);
}
fout << max_overall << " ";
for(int i = 0; i < ok_idx; i++){
if((values_xor[i] ^ values_xor[ok_idx]) == max_overall){
fout << i + 2 << " " << ok_idx + 1<< '\n';
break;
}
}
return 0;
}