Cod sursa(job #2114881)

Utilizator giotoPopescu Ioan gioto Data 25 ianuarie 2018 23:23:27
Problema Xor Max Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.98 kb
#include <bits/stdc++.h>
using namespace std;

int n, x, y, Sum, Max;
int l, r;
char s[25];
struct Trie{
    int w;
    Trie *fiu[3];
    Trie(){
        w = n + 1;
        memset(fiu, 0, sizeof(fiu));
    }
};
Trie *T = new Trie;
inline void add(Trie *nod, char *p, int i){
    if(*p == NULL){
        nod->w = min(nod->w, i);
        return ;
    }
    if(nod->fiu[*p - '0'] == 0)
        nod->fiu[*p - '0'] = new Trie;
    add(nod->fiu[*p - '0'], p + 1, i);
}
inline void find(Trie *nod, char *p, int put, int i){
    if(*p == NULL){
        if(Sum > Max){
            Max = Sum;
            l = nod->w + 1;
            r = i;
        }
        else if(Sum == Max && r == i && (r - l + 1 > i - nod->w))
            l = nod->w + 1;
        return ;
    }
    if(nod->fiu[1 - (*p - '0')] == 0){
        if(*p - '0' == 1) Sum = Sum - put;
        find(nod->fiu[*p - '0'], p + 1, put / 2, i);
        return ;
    }
    if(*p - '0' == 0) Sum = Sum + put;
    find(nod->fiu[1 - (*p - '0')], p + 1, put / 2, i);
}
inline void get(int x){
    int p = 1, put;
    while(p <= x) p = p << 1;
    p = p >> 1;
    int NR = 0;
    while(x > 0 || p > 0){
        if(x >= p){
            x = x - p;
            s[NR++] = '1';
        }
        else s[NR++] = '0';
        p = p >> 1;
    }
    for(int i = 20, j = NR - 1; j >= 0 ; --i, --j)
        s[i] = s[j];
    for(int j = 0; j <= 20 - NR ; ++j)
        s[j] = '0';
}
int main()
{
    freopen("xormax.in", "r", stdin);
    freopen("xormax.out", "w", stdout);
    scanf("%d", &n);
    scanf("%d", &x);
    Max = x; y = x; l = 1; r = 1;
    get(x);
    add(T, s, 1);
    for(int i = 2; i <= n ; ++i){
        scanf("%d", &x);
        y = y ^ x;
        if(x > Max) Max = x, l = i, r = i;
        if(y > Max) Max = y, l = 1, r = i;
        Sum = y;
        get(y);
        int put = 1 << 20;
        find(T, s, put, i);
        add(T, s, i);
    }
    printf("%d %d %d", Max, l, r);
    return 0;
}