Cod sursa(job #989795)

Utilizator smaraldaSmaranda Dinu smaralda Data 26 august 2013 15:01:37
Problema Xor Max Scor 65
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.04 kb
#include<cstdio>
#include<cstring>
#include<set>
#include<algorithm>
#define NMAX 100000
using namespace std;

int i,len,pos[NMAX+5],xp[NMAX+5];
char s[25];

struct TRIE {
    set <int> pos;
    TRIE *edges[2];
    };

TRIE *init (TRIE *node) {
    if(node == NULL)
        node = new TRIE;
    node->edges[0] = node->edges[1] = NULL;
    return node;
}

TRIE *add (TRIE *ver, char *str) {
    if(str[0] == NULL)
        ver->pos.insert(i);
    else    {
        int ind = str[0] - '0';
        if(ver->edges[ind] == NULL)
            ver->edges[ind] = init(ver->edges[ind]);
        ++str;
        ver->edges[ind] = add(ver->edges[ind],str);
        }
    return ver;
}

int cauta (TRIE *ver, char *str) {
    if(str[0] == NULL)
        return *(ver->pos.begin());
    else    {
        int ind = str[0] - '0';
        ++str;
        if(ver->edges[!ind] == NULL)
            return cauta(ver->edges[ind],str);
        else
            return cauta(ver->edges[!ind],str);
        }
}

void b2 (int x, char *str) {
    int st,dr,num = -1;
    while(x) {
        str[++num] = (x & 1) + '0';
        x >>= 1;
        }
    while(num < 20)
        str[++num] = '0';
    st = 0;
    dr = num - 1;
    while(st < dr) {
        swap(str[st],str[dr]);
        st++;
        dr--;
        }
    str[num] = NULL;
}

int main() {
    freopen("xormax.in","r",stdin);
    freopen("xormax.out","w",stdout);
    char str[22];
    int n,x,val,valmax,st,dr;
    TRIE *start = NULL;
    start = init(start);
    scanf("%d",&n);
    i = 0;
    b2(0,str);
    add(start,str);
    for(i = 1; i <= n; i++) {
        scanf("%d",&x);
        xp[i] = xp[i-1] ^ x;
        b2(xp[i],str);
        add(start,str);
        pos[i] = cauta(start,str);
        }
    valmax = 0;
    for(i = 1; i <= n; i++) {
        val = xp[i] ^ xp[pos[i]];
        if(val > valmax) {
            valmax = val;
            st = pos[i] + 1;
            dr = i;
            }
        }
    printf("%d %d %d\n",valmax,st,dr);
    return 0;
}