Pagini recente » Cod sursa (job #2684040) | Istoria paginii runda/simulare1112/clasament | Cod sursa (job #2857444) | Cod sursa (job #1849966) | Cod sursa (job #1995720)
#include <iostream>
#include <fstream>
#define BAD_VALUE 100000
using namespace std;
typedef struct Trie {
unsigned int *index;
struct Trie *children[2];
} TrieT, *TrieP;
void addToTrie(TrieP node, const unsigned int value, const unsigned int arrayIndex){
unsigned char bitIndex = 21;
bool bits[21];
unsigned int mask = 1 << 20;
while(bitIndex--){
bits[bitIndex] = (bool)(value & mask);
mask >>= 1;
}
bitIndex = 21;
TrieP newCell;
while(bitIndex--){
if(node->children[bits[bitIndex]] == NULL){
newCell = new TrieT;
newCell->index = NULL;
newCell->children[0] = newCell->children[1] =
NULL;
node->children[bits[bitIndex]] = newCell;
node = newCell;
} else
node = node->children[bits[bitIndex]];
}
if(!node->index)
node->index = new unsigned int;
*(node->index) = arrayIndex;
}
unsigned int getBestValue(TrieP node, unsigned int value, unsigned int &index){
if(!node->children[0] && !node->children[1]){
index = BAD_VALUE;
return 0;
}
unsigned char bitIndex = 21;
bool bits[21];
unsigned int mask = 1 << 20;
while(bitIndex--){
bits[bitIndex] = (bool)(value & mask);
mask >>= 1;
}
bitIndex = 21;
mask = 0;
while(bitIndex--)
if(node->children[!bits[bitIndex]]){
node = node->children[!bits[bitIndex]];
mask += !bits[bitIndex] << bitIndex;
}
else{
if(bits[bitIndex]){
index = BAD_VALUE;
return 0;
}
node = node->children[bits[bitIndex]];
mask += bits[bitIndex] << bitIndex;
}
index = mask ? *(node->index) : BAD_VALUE;
return mask;
}
void freeTrie(TrieP node){
if(node->index)
delete node->index;
else{
if(node->children[0])
freeTrie(node->children[0]);
if(node->children[1])
freeTrie(node->children[1]);
}
delete node;
}
int main() {
fstream file ("xormax.in", ios::in);
unsigned int N, l_sum, g_max, g_st, g_fi, value, index, bestSum;
TrieP root = new TrieT;
root->index = NULL;
root->children[0] = root->children[1] = NULL;
file >> N;
file >> l_sum;
g_max = l_sum;
g_fi = g_st = 0;
addToTrie(root, g_max, 0);
for(unsigned i = 1; i < N; i++){
file >> value;
l_sum ^= value;
addToTrie(root, l_sum, i);
bestSum = getBestValue(root, l_sum, index);
if(index != BAD_VALUE){
g_st = index + 1;
g_fi = i;
g_max = bestSum ^ l_sum;
}
}
file.close();
freeTrie(root);
//delete root;
file.open("xormax.out", ios::out);
file << g_max << " " << g_st + 1 << " " << g_fi + 1;
file.close();
return 0;
}