Cod sursa(job #1722520)

Utilizator cristina_borzaCristina Borza cristina_borza Data 28 iunie 2016 12:23:07
Problema Xor Max Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.78 kb
#include <fstream>
#include <cstring>

using namespace std;

ifstream f("xormax.in");
ofstream g("xormax.out");

int n , aux , start , stop , en , x , ans;
int s[100005];

char sir[50];

struct Trie {
    int lst;
    Trie *fiu[5];

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

Trie *Root = new Trie;

void adauga(Trie *node , char *s , int pos) {
    if(*s == '\0') {
        node -> lst = pos;
        return;
    }

    int qq = *s - '0';
    if(node -> fiu[qq] == NULL) {
        node -> fiu[qq] = new Trie;
    }

    adauga(node -> fiu[qq] , s + 1 , pos);
}

void query(Trie *node , char *s , int p) {
    if (*s == '\0') {
        en = node -> lst;
        return;
    }

    int qq = *s - '0';
    if (node -> fiu[1 - qq] != NULL) {
        aux = aux + (1 << p);
        query(node -> fiu[1 - qq] , s + 1 , p - 1);
    }

    else {
        if (node -> fiu[qq] != NULL)
            query(node -> fiu[qq] , s + 1 , p - 1);
    }
}

void calc_sir (int val) {
    memset(sir , 0 , sizeof(sir));
    int nr = 25;

    while (nr >= 0) {
        if (val >= (1 << nr)) {
            sir[25 - nr] = '1';
            val -= (1 << nr);
        }

        else {
            sir[25 - nr] = '0';
        }

        --nr;
    }
}

int main() {
    f >> n;

    ans = -1;

    calc_sir(0);
    adauga(Root , sir , 0);

    for (int i = 1; i <= n; ++i) {
        f >> x;
        s[i] = (s[i - 1] ^ x);

        calc_sir(s[i]);

        aux = 0;
        query(Root , sir , 25);

        if (aux > ans) {
            ans = aux;
            start = en + 1;
            stop = i;
        }

        adauga(Root , sir , i);
    }

    g << ans << " " << start << " " << stop;
    return 0;
}