Cod sursa(job #2104880)

Utilizator CammieCamelia Lazar Cammie Data 12 ianuarie 2018 13:06:06
Problema Xor Max Scor 85
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.12 kb
#include <fstream>
#include <cstring>

#define MAXN 100005

using namespace std;

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

struct trie{
    int bg, cnt;
    trie *son[2];

    trie() {
        bg = cnt = 0;

        memset(son, 0, sizeof(son));
    }
};

trie *root = new trie();

int N, nn, v[MAXN], x[MAXN], val, sol = 0, in, sf, stop;
int auxiliar;

inline void Read() {
    fin >> N;

    int maxim = 0;

    for (int i = 1; i <= N; i++) {
        fin >> v[i];

        maxim = max(v[i], maxim);
    }

    while (maxim) {
        maxim /= 2;
        nn++;
    }
}

inline void Add(trie *node, int poz) {
    if (poz > nn) { ///daca am ajuns la sj reprezentarii binare
        node->bg = stop;
        node->cnt = val;
        return;
    }

    if (node->son[x[poz]] == NULL) {
        node->son[x[poz]] = new trie();
    }

    Add(node->son[x[poz]], poz + 1);
}

inline void Test(trie *node, int poz) {
    if (poz > nn + 1) ///daca s-a terminat sirul
        return;

    int delta = !x[poz];

    if (node->cnt > 0) {
        auxiliar = (node->cnt ^ val);

        if (auxiliar > sol) {
            sol = auxiliar;
            in = node->bg + 1;
            sf = stop;
        }
        else if (auxiliar == sol && sf == stop) {
            if (sf - in + 1 > stop - node->bg)
                sf = stop,
                in = node->bg;
        }
    }

    if (node->son[delta] == NULL) {
         Test(node->son[!delta], poz + 1);
    }
    else {
        Test(node->son[delta], poz + 1);
    }
}

inline void Adauga() {
    int aux, j;

    for (int i = 1; i <= N; i++) {
        if (v[i] > sol) {
            sol = v[i];
            in = i;
            sf = i;
        }

        aux = v[i]; j = nn; stop = i;
        val = val ^ v[i];

        while (aux) {
            x[j] = (x[j] ^ (aux % 2));
            aux /= 2;
            j--;
        }

        Add(root, 1);
        Test(root, 1);
    }

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

int main () {
    Read();
    Adauga();

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