Cod sursa(job #953012)

Utilizator primulDarie Sergiu primul Data 24 mai 2013 17:57:03
Problema Xor Max Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.71 kb
//sumxor[i]=a[1]^a[2]^a[3]^...^a[i]
//introducem in trie bitii unei sume xor
//incepand cu cel mai semnificativ si retinand pozitia
//sumxor[i]^sumxor[j-1] = a[j]^a[j+1]^...^a[i]
#include <fstream>
#define In "xormax.in"
#define Out "xormax.out"
#define Nmax 100010
#define maxb 22
using namespace std;
int sumxor[Nmax];
struct Trie
{
    int poz;
    Trie *b[2];
    Trie()
    {
        poz = 0;
        b[0] = b[1] = 0;
    }
};
Trie *T = new Trie;
//introducem suma xor x in trie incepand cu bitul cel mai semnificativ
inline void Adauga(Trie *nod, int x,int poz)
{
    int i;
    bool bit;
    for(i = maxb;i >= 0;i--)
    {
        bit = (x & (1<<i));//valoarea bitului de pe pozitia i
        if(nod->b[bit]==0)
            nod->b[bit] = new Trie;
        nod = nod ->b[bit];
    }
    nod -> poz = poz;
}
//cautam in trie o pozitia care ar face suma xor maxima
inline int Cauta(Trie *nod,int x)
{
    int i;
    bool bit;
    for(i = maxb;i >= 0 ;i--)
    {
        bit = (x&(1<<i));
        if(nod->b[!bit]!=0)//caut bitul opus pentru a maximiza suma xor
            nod = nod->b[!bit];
        else
            nod = nod->b[bit];
    }
    return nod -> poz;
}
int main()
{
    int i, N, x,j,sol = -1,st,dr;
    ifstream f(In);
    f >> N;
    Adauga(T,0,0);
    for(i = 1;i <= N ; i++)
    {
        f >> x;
        sumxor[i] = (sumxor[i-1]^x);
        j = Cauta(T,sumxor[i]);
        if(sol < (sumxor[i] ^ sumxor[j]))
        {
            sol = sumxor[i] ^ sumxor[j];
            st = j+1;
            dr = i;
        }
        Adauga(T,sumxor[i],i);
    }
    f.close();
    ofstream g(Out);
    g<<sol<<" "<<st<<" "<<dr<<"\n";
    g.close();
    return 0;
}