Cod sursa(job #282739)

Utilizator sandyxpSanduleac Dan sandyxp Data 18 martie 2009 09:55:53
Problema Xor Max Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.71 kb
#include <fstream>
#include <cstring>
#include <vector>
using namespace std;

ifstream fi("xormax.in");
ofstream fo("xormax.out");
#define MN 100001


struct Trie {
    int care;
    Trie* fiu[2];
} *Root = new Trie;

int N, A[MN], mbits;
int xormax = 0;
int lnod, rnod;

Trie *ins(Trie *p, int nr, int mask, int poz)
{
    if (mask >= 0) {
        Trie * &Dest = p->fiu[(nr >> mask) & 1];
        if (Dest == 0)
            Dest = new Trie;
        ins(Dest, nr, mask-1, poz);
    } else
        //p->care.push_back(poz);
        p->care = poz;
}

int bits(int nr) {
    // max 21
    int step = 16, i;
    for (i = 0; step; step >>= 1)
        if (i+step <= 21 && (nr >> i+step))
            i += step;
    return i+1;
}

#define lbit (config & 1)

void guess(Trie *p, int config, int shift) {
    int last = 1, tmp;
    for (int i = 0; i < 2; ++i)
        if (p->fiu[i]) {
            guess(p->fiu[i], config + (i<<shift), shift+1);
            last = 0;
        }
    if (last) {
        Trie *n = Root;
        for (; shift--; config >>= 1) {
                n = n->fiu[!lbit] ? n->fiu[!lbit] :
                    n->fiu[lbit];
        }
        // check it !
        if ((tmp = A[p->care] ^ A[n->care]) > xormax) {// sau egal !
            lnod = p->care, rnod = n->care, xormax = tmp;
        }
    }
}

int main()
{
    int i, x, mask;
    fi >> N;
    Trie *a = new Trie;
    for (i = 1; i <= N; ++i) {
        fi >> x;
        A[i] = i ? A[i-1] ^ x : x;
        mbits = max(bits(A[i]), mbits);
    }
    mask = mbits-1;
    for (i = 1; i <= N; ++i) {
        ins(Root, A[i], mask, i);
    }
    guess(Root->fiu[1], 1, 1);
    
    fo << xormax << " " << min(lnod,rnod)+1 << " " << max(lnod,rnod) << "\n";
    fo.close();
    return 0;
}