Pagini recente » Cod sursa (job #2601770) | Cod sursa (job #1921764) | Cod sursa (job #2360095) | Cod sursa (job #1771480) | Cod sursa (job #1420071)
#include <fstream>
#include <cstring>
using namespace std;
const int Nmax = 100005;
int N;
int a[Nmax];
int R[Nmax]; // R[i] = suma xor pe [i,N]
int L[Nmax]; // L[i] = suma xor pe [1,i]
int A; // A = suma xor pe [1,N]
// a[i] ^ a[i+1] ^ ... ^ a[j] = A ^ R[j+1] ^ L[i-1] are valoare maxima cand (A ^ R[j+1]) ^ L[i-1] are valoare maxima
// pentru fiecare j caut un i pentru care A^R[j]^L[i] are val max
// ca sa il caut pe L[i] folosesc un Trie in care introduc fiecare L[i] in baza 2
// ca suma xor sa fie cat mai mare trebuie sa avem biti diferiti in cele doua numere pe aceeasi pozitie
// incep de la cel mai mare bit (20) si daca numarul (A ^ R[j]) are bitul setat, atunci L[i] trebuie sa aibe acest bit 0
// ca suma xor sa fie cat mai mare, iar daca nu pot sa ma duc in 0 atunci ma duc in 1, la fel fac si daca bitul nu este setat
// asta imi asigura pozitia i pentru care valoarea R[j]^A^L[i] este maxima
struct Trie
{
Trie* edge[2];
int endhere;
Trie() {
memset(edge,0,sizeof edge);
endhere = 0;
}
};
Trie *T = new Trie();
void Add(Trie *T,int val,int bit,int pos)
{
if(bit == -1) {
T->endhere = pos;
return;
}
int next = ((1<<bit)&val) > 0 ? 1 : 0;
if(T->edge[next] == 0)
T->edge[next] = new Trie();
Add(T->edge[next],val,bit-1,pos);
}
int query(Trie *T,int val,int bit)
{
if(bit == -1)
return T->endhere;
int next = ((1<<bit)&val) > 0 ? 1 : 0;
if(T->edge[!next] != 0)
next = !next;
return query(T->edge[next], val, bit-1);
}
int main()
{
ifstream fin("xormax.in");
ofstream fout("xormax.out");
fin >> N;
for(int i = 1; i <= N; i++)
fin >> a[i];
R[N] = a[N];
for(int i = N-1; i >= 1; i--)
R[i] = a[i]^R[i+1];
L[1] = a[1];
for(int i = 2; i <= N; i++)
L[i] = a[i]^L[i-1];
A = L[N];
int BestSum = 0, Start = 1, End = 1;
L[0] = 0;
R[N+1] = 0;
for(int j = 2; j <= N + 1; j++) {
Add(T,L[j-2],20,j-2);
int i = query(T, A ^ R[j], 20);
int currSum = A ^ R[j] ^ L[i];
if(currSum > BestSum || (currSum == BestSum && (j - 1 < End || (j-1 == End && j - i - 2 < End - Start)))) {
BestSum = currSum;
Start = i + 1;
End = j - 1;
}
}
fout << BestSum << " " << Start << " " << End << "\n";
}