Cod sursa(job #469233)

Utilizator APOCALYPTODragos APOCALYPTO Data 6 iulie 2010 23:55:38
Problema Xor Max Scor 70
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.62 kb
#include <iostream>
using namespace std;
#define maxn 100010
#define inf 99999999
#define transf(x) ~x

int N, A[maxn], S[maxn];
int nr, poz;

struct Trie {
    int k;
    Trie *fiu[2];

    Trie() {
         k = 0;
         memset(fiu, 0, sizeof(fiu));
    }
};

Trie *T = new Trie;


void add(Trie *q, int b) {
    if(b == -1) {
         q -> k = poz;
         return;
    }

    int next = nr & (1 << b);
    if(next) next = 1;
    if(!q -> fiu[next]) {
         q -> fiu[next] = new Trie;
    }

    add(q -> fiu[next], b-1);
}

int search(Trie *q, int b) {
    if(b == -1) {
         return q -> k;
    }

    int next = nr & (1 << b);
    if(next) next = 1;
    if(!q -> fiu[next]) {
          if(!next) next = 1;
          else next = 0;
    }
    if(!q -> fiu[next]) {
         return 0;
    }

    return search(q -> fiu[next], b-1);
}

int main() {
    FILE *f1=fopen("xormax.in", "r"), *f2=fopen("xormax.out", "w");
    int i, p, q;
    fscanf(f1, "%d\n", &N);
    for(i=1; i<=N; i++) {
         fscanf(f1, "%d", &A[i]);
         S[i] = S[i-1] ^ A[i];
    }

    nr = 0, poz = 0;
    add(T, 21);

    int sol = -inf, start = 0, finish = 0;
    for(i=1; i<=N; i++) {
         nr = transf( S[i] );
         p = search(T, 21);
         if(sol < (S[i] ^ S[p])) {
              sol = S[i] ^ S[p];
              start = p + 1;
              finish = i;
         }
         nr = S[i];
         poz = i;
         add(T, 21);
    }
    if(start!=finish)
    fprintf(f2, "%d %d %d\n", sol, start, finish);
    else
    for(;;);
    fclose(f1); fclose(f2);
    return 0;
}