Cod sursa(job #288376)

Utilizator flamecataCiobanu Alexandru-Catalin flamecata Data 25 martie 2009 19:05:44
Problema Xor Max Scor 100
Compilator cpp Status done
Runda aa Marime 1.75 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;   
}