Pagini recente » Cod sursa (job #1489889) | Cod sursa (job #1014474) | Cod sursa (job #555331) | Cod sursa (job #2748431) | Cod sursa (job #598538)
Cod sursa(job #598538)
#include <cstdio>
#include <vector>
using namespace std;
const int N = 100005;
vector< vector < pair <int , char> > > t;
vector<int> trie;
vector<char> number;
int n, p[21];
inline int get_edge(int root, char c) {
int i;
for(i = 0 ;i < t[root].size(); ++i)
if(t[root][i].second == c)
return t[root][i].first;
return -1;
}
inline void add(vector<char> number, int ind) {
int next;
int i, root = 0;
for(i = 0; i < number.size(); ++i) {
next = get_edge(root, number[i]);
if(next == -1) {
next = trie.size();
trie.push_back(0);
t.resize(trie.size());
t[root].push_back(make_pair(next, number[i]));
}
root = next;
}
trie[root] = ind;
}
inline pair<int, int> find(vector<char> number) {
int i, root = 0, next, j, sw, suma = 0;
for(i = 0; i < number.size(); ++i){
sw = 0;
for(j = 0; j < t[root].size(); ++j)
if(t[root][j].second != number[i]){
next = t[root][j].first;
sw = 1;
suma += p[20 - i];
}
if(sw == 0)
for(j = 0; j < t[root].size(); ++j)
if(t[root][j].second == number[i])
next = t[root][j].first;
root = next;
}
return make_pair(trie[root] + 1, suma);
}
int main() {
freopen("xormax.in", "r", stdin);
freopen("xormax.out", "w", stdout);
int i, a, max = 0, start = 1, stop = 2, s = 0;
scanf("%d", &n);
p[0] = 1;
for(i = 1; i <= 22; ++i)
p[i] = p[i - 1] * 2;
trie.reserve(p[21] + 3); trie.resize(1);
t.reserve(p[21] + 3); t.resize(1);
for(int j = 1; j <= n; ++j) {
scanf("%d ", &a);
s ^= a;
number.clear();
for(i = 20; i >= 0; --i){
int sw = p[i] & s;
number.push_back(sw > 0 ? 1 : 0);
}
// for(i = 0; i < number.size(); ++i)
// printf("%d", number[i]);
// printf("\n");
pair<int, int> rez;
if(j > 1){
rez = find(number);
if(max < rez.second) {
max = rez.second;
start = rez.first;
stop = j;
}
// printf("%d %d\n", rez.first, rez.second);
}
add(number, j);
}
printf("%d %d %d\n", max, start, stop);
return 0;
}