Cod sursa(job #282758)

Utilizator sandyxpSanduleac Dan sandyxp Data 18 martie 2009 10:26:29
Problema Xor Max Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.47 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 = 1, rnod = 1;

void 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 tmp, config = A[which];
    int shift = mbits;
    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 = n->care+1, rnod = which, xormax = tmp;
    }
}

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