Pagini recente » Cod sursa (job #3183851) | Cod sursa (job #505259) | Cod sursa (job #1122243) | Cod sursa (job #2402606) | Cod sursa (job #841515)
Cod sursa(job #841515)
#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>
#include <set>
#include <queue>
#include <deque>
using namespace std;
ifstream f("xormax.in");
ofstream g("xormax.out");
#define nmax 3200005
#define ll long long
struct trie{
int cuv, fiu;
}T[nmax][3];
//campul camp imi va zice daca in acel nod se termina un cuvant si daca da pe ce pozitie
int n, a[nmax], sum[nmax], nr_tot, aux[nmax];
int aux2[nmax];
int Max = 0, St, Dr;
void citeste(){
f >> n;
for(int i=1; i<=n; ++i) f >> a[i], sum[i] = sum[i-1] ^ a[i];
}
void bagaBiti(int x){
aux[0] = 0; aux2[0] = 0;
while(x){
aux[++aux[0]] = x % 2; aux2[++aux2[0]] = aux[ aux[0] ];
x = x >> 1;
}
// ii inversez pentru ca la inceput sa fie cel mai semnificativ bit;
for(; aux[0] <32; aux[++aux[0]] = 0, aux2[++aux2[0]] = 0);
for(int i=1, j=aux[0]; i<=aux[0]; ++i, --j) aux[i] = aux2[j];
}
void fa_max(int X, int ord){
int Ceva = sum[X] ^ sum[ord];
if ( Ceva > Max){
Max = Ceva; St = ord+1; Dr = X;
}else if ( Ceva == Max){
if (X < Dr){
St = ord+1; Dr = X;
}else if (X == Dr && X - (ord+1)+1 < Dr-St+1){
St = ord+1; Dr = X;
}
}
}
void cauta(int nod, int poz, int X){
if (poz > 1){
int bit2 = aux[poz-1];
if (T[nod][1^bit2].cuv != 0){
fa_max( X, T[nod][1^bit2].cuv );
}else if (T[nod][bit2].cuv!=0){
fa_max( X, T[nod][bit2].cuv);
}
}
if (poz == aux[0]+1) return;
int bit = aux[poz];
if (T[nod][1^bit].fiu != 0){
cauta( T[nod][1^bit].fiu, poz+1, X );
}else if (T[nod][bit].fiu != 0){
cauta( T[nod][bit].fiu, poz+1, X );
}else return;
}
void baga(int nod, int poz, int Ord){
if (poz == aux[0]+1){
T[nod][ aux[poz-1] ].cuv = Ord;// al cate-lea cuvant e asta(din alea n
return;
}
int bit = aux[poz];
if (T[nod][bit].fiu != 0){
baga(T[nod][bit].fiu, poz+1, Ord);
}else {
T[nod][bit].fiu = ++nr_tot;
baga(nr_tot, poz+1, Ord);
}
}
void rezolva(){
// ideea ar fi ca fac xor partiale sum[i] = 1^2^..^i;
// acum vreau sa caut pentru fiecare i un j (j < i) a. i. S[i] ^ S[j] sa fie maxim;
// de ex S[i] = 100111
// =>best S{j] = 011000;// asa ca incerc sa obtin cel mai bun j; pentru asta tin un trie si il caut in el
Max = 0;
//cout << (sum[8] ^ sum[5]) << " " << sum[8] << " " << sum[5] << "\n";
for(int i=1; i<=n; ++i){
bagaBiti(sum[i]);// pornesc de la cel mai semnificativ bit
cauta(0, 1, i);
baga(0, 1, i);
if (sum[i] > Max){
sum[i] = Max; St = 1; Dr = i;
}
//g << Max <<" " << St << " " << Dr << "\n";
}
//cout << Max <<" " << St << " " << Dr << "\n";
if (Max != 0) g << Max <<" " << St << " " << Dr << "\n";
else g << 0 << " " << 1 << " " << 1 << "\n";
}
int main(){
citeste();
rezolva();
f.close();
g.close();
return 0;
}