Cod sursa(job #1922153)

Utilizator raulmuresanRaul Muresan raulmuresan Data 10 martie 2017 16:13:21
Problema Xor Max Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.4 kb
#include<fstream>
#include<vector>
#include<string>

using namespace std;

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

const int MAX = 1e5 + 5;
int maxx, s[MAX], n, maxi = 1, maxj = 1, max_sum;

struct Trie {
    int index;
    Trie* f[2];

    Trie() {
        f[0] = NULL;
        f[1] = NULL;
        index = 0;
    }
};

Trie * root = new Trie();

void add_sum(Trie* nod, int sum, int poz, int i) {
    if (poz == -1) {
        nod -> index = i;
        return;
    }
    int bit = ((1 << poz) & sum ? 1 : 0);
    if (nod -> f[bit] == NULL)
        nod -> f[bit] = new Trie();

    add_sum(nod -> f[bit], sum, poz - 1, i);
}

int xor_max(Trie* nod, int sum, int poz, int& maxx) {
    if (poz == -1)
        return nod -> index;

    int bit = ((1 << poz) & sum ? 0 : 1);
    if (nod -> f[bit] != NULL)
        maxx = ((1 << poz) ^ maxx);
    else
        bit = (bit ? 0 : 1);

    xor_max(nod -> f[bit], sum, poz - 1, maxx);
}

int main() {
    fin >> n;
    for (int temp, nr, i = 1; i <= n; i++) {
        fin >> nr;

        s[i] = s[i - 1] ^ nr;
        add_sum(root, s[i], 20, i);

        maxx = 0;
        temp = xor_max(root, s[i], 20, maxx);
        if (maxx > max_sum) {
            max_sum = maxx;
            maxi = temp + 1;
            maxj = i;
        }
    }
    fout << max_sum << ' ' << maxi << ' ' << maxj;
    return 0;
}