Pagini recente » Cod sursa (job #893286) | Cod sursa (job #337050) | Cod sursa (job #3354580) | Monitorul de evaluare | Cod sursa (job #3354601)
// So a not optimal solution in O(n^2) is keeping prefix xor sums
// This solution gets 40p
// #include <fstream>
// #include <vector>
// std::ifstream fin("xormax.in");
// std::ofstream fout("xormax.out");
// int N;
// std::vector<int> v;
// int main() {
// fin >> N;
// v.resize(N);
// for (int& x : v) {
// fin >> x;
// }
// std::vector<int> prefix_sum = v;
// for (int i = 1; i < N; ++i) {
// prefix_sum[i] = prefix_sum[i - 1] ^ v[i];
// }
// int max = -1, st = -1, dr = -1;
// for (int i = 0; i < N; ++i) {
// for (int j = i; j < N; ++j) {
// int curr = prefix_sum[j] ^ (i == 0 ? 0 : prefix_sum[i - 1]);
// if (curr > max) {
// max = curr;
// st = i;
// dr = j;
// }
// else if(curr == max) {
// if (dr > j){
// st = i;
// dr = j;
// }
// else if(dr == j && dr - st > j - i){
// st = i;
// dr = j;
// }
// }
// }
// }
// fout << max << ' ' << st + 1 << ' ' << dr + 1;
// }
#include <fstream>
#include <vector>
std::ifstream fin("xormax.in");
std::ofstream fout("xormax.out");
int N;
std::vector<int> v;
int main() {
fin >> N;
v.resize(N);
for (int& x : v) {
fin >> x;
}
int xor_sum = 0, maxim = -1, st = -1, dr = -1, last_start = 0;
for (int i = 0; i < N; ++i) {
if (v[i] > (xor_sum ^ v[i])) {
xor_sum = v[i];
last_start = i;
}
else {
xor_sum ^= v[i];
}
if (xor_sum > maxim) {
maxim = xor_sum;
st = last_start;
dr = i;
}
}
fout << maxim << ' ' << st + 1 << ' ' << dr + 1;
}