Cod sursa(job #2104944)

Utilizator CammieCamelia Lazar Cammie Data 12 ianuarie 2018 13:55:23
Problema Xor Max Scor 90
Compilator cpp Status done
Runda Arhiva de probleme Marime 2 kb
///fie xi = v1 ^ v2 ^...^vi si xj = v1^v2^...^vj
///atunci xi ^ xj = (v[j + 1] ^ v[j + 2]^...^v[i]);
///a^b^a = b pentru ca a ^ a = 0 mereu

///astfel, pentru fiecare x[i] determinat caut x[j] calculat anterior astfel incat xi ^ xj sa fie maxim
///stiind ca a ^ b e 1 doar cand a != b(unde a, b apartin multimii {0, 1}), pentru fiecare cifra binara din x[i] incercam sa mergem pe opusa ei
///astfel, daca xi[k] = e 1, atunci incercam sa mergem pe 0 in trie pentru a obtine o valoare cat mai mare(unde xi[1] = cel mai semnificativ bit)

#include <fstream>

#define MAXN 100005

using namespace std;

ifstream fin("xormax.in");
ofstream fout("xormax.out");

struct TRIE{
    int val;
    TRIE *son[2];

    TRIE()
    {
        val = 0;
        son[0] = son[1] = NULL;
    }
};

TRIE *root = new TRIE();

int s[MAXN];

inline void Add(TRIE *NODE, int p, int num, int poz) {
    if (p == -1) {
        NODE->val = poz;
        return;
    }
    bool bit = num & (1 << p); ///testez daca bitul la care am ajuns e 1 sau 0

    if (NODE->son[bit] == NULL) {
        NODE->son[bit] = new TRIE();
    }

    Add(NODE->son[bit], p - 1, num, poz);
}

inline int Search(TRIE *NODE, int p, int num) {
    if (p == -1)
        return NODE->val;
    bool bit = num & (1 << p);

    if (NODE->son[!bit] == NULL)
        return Search(NODE->son[bit], p - 1, num);
    return Search(NODE->son[!bit], p - 1, num);
}

inline void Read() {
    int sol = 0, in = 0, sf = 0, N, nr, poz;

    fin >> N;

    Add(root, 21, 0, 0); ///il adaug pe 0 - pentru a obtine si solutia 1...i

    for (int i = 1; i <= N; i++) {
        fin >> nr;
        s[i] = s[i - 1] ^ nr;
        Add(root, 21, s[i], i);

        poz = Search(root, 21, s[i]);

        if ((s[poz] ^ s[i]) > sol) {
            sol = s[poz] ^ s[i];
            in = poz + 1;
            sf = i;
        }
    }

    fout << sol << " " << in << " " << sf;
}

int main () {
    Read();

    fin.close(); fout.close(); return 0;
}