Cod sursa(job #841483)

Utilizator vendettaSalajan Razvan vendetta Data 24 decembrie 2012 12:15:34
Problema Xor Max Scor 40
Compilator cpp Status done
Runda Arhiva de probleme Marime 3.15 kb
#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 100004
#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;
int Nr = 0;
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){
    //Nr = sum[ord];
    int Ceva = sum[X] ^ Nr;
    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;
        }
    }
    //g << X << " " << sum[ord] << " " << ord+1 << "\n";

}

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){
        Nr = Nr * 2 + (1^bit);
        cauta( T[nod][1^bit].fiu, poz+1, X );
    }else if (T[nod][bit].fiu != 0){
        Nr = Nr * 2 + bit;
        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
        //for(int i=1; i<=aux[0]; ++i) cout << aux[i];
        //cout << '\n';
        Nr = 0;
        cauta(0, 1, i);
        baga(0, 1, i);
        //g << Max <<" " <<  St << " " << Dr << "\n";
    }
    //cout << Max <<" " <<  St << " " << Dr << "\n";
    g << Max <<" " <<  St << " " << Dr << "\n";
}

int main(){
    citeste();
    rezolva();

    f.close();
    g.close();

    return 0;
}