Mai intai trebuie sa te autentifici.
Cod sursa(job #3140655)
Utilizator | Data | 8 iulie 2023 10:51:47 | |
---|---|---|---|
Problema | Xor Max | Scor | 100 |
Compilator | cpp-64 | Status | done |
Runda | Arhiva de probleme | Marime | 1.09 kb |
#include <bits/stdc++.h>
using namespace std;
ifstream fin("xormax.in");
ofstream fout("xormax.out");
struct Trie {
int poz;
Trie* next[2];
Trie() : poz(0), next{} {}
};
int l, r, s[100001], n, a[100001], ans = -1, cauta, Max = -1;
int Find(Trie* root, int w) {
for (int i = 20; i >= 0; --i) {
int c = (w >> i) & 1;
if (root->next[1 - c] != nullptr)
root = root->next[1 - c];
else
root = root->next[c];
}
return root->poz;
}
void Add(Trie* root, int w, int ind) {
for (int i = 20; i >= 0; --i) {
int c = (w >> i) & 1;
if (root->next[c] == nullptr)
root->next[c] = new Trie();
root = root->next[c];
}
root->poz = ind;
}
int main() {
fin >> n;
Trie* root = new Trie();
Add(root, 0, 0);
for (int i = 1; i <= n; ++i) {
fin >> a[i];
s[i] = s[i - 1] ^ a[i];
cauta = Find(root, s[i]);
ans = s[i] ^ s[cauta];
if (ans > Max) {
Max = ans;
l = cauta + 1;
r = i;
}
Add(root, s[i], i);
}
fout << Max << ' ' << l << ' ' << r << '\n';
return 0;
}