Cod sursa(job #1420071)

Utilizator tudi98Cozma Tudor tudi98 Data 17 aprilie 2015 15:44:22
Problema Xor Max Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.46 kb
#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";

}