Cod sursa(job #282743)

Utilizator sandyxpSanduleac Dan sandyxp Data 18 martie 2009 10:02:01
Problema Xor Max Scor 5
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.49 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 = 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 >> shift) & 1)

void guess(int which, int shift) {
    int tmp, config = A[which];
    Trie *n = Root;
    while (shift--) {
        n = n->fiu[!lbit] ? n->fiu[!lbit] :
            n->fiu[lbit];
    }
    // check it !
    if ((tmp = config ^ A[n->care]) > xormax) { // sau egal !
        lnod = which, 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);
    }
    for (i = 1; i <= N; ++i) {
        guess(i, mbits);
    }
    
    fo << xormax << " " << min(lnod,rnod)+1 << " " << max(lnod,rnod) << "\n";
    fo.close();
    return 0;
}