Cod sursa(job #1110317)

Utilizator deneoAdrian Craciun deneo Data 17 februarie 2014 22:55:04
Problema Xor Max Scor 25
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.02 kb
#include <iostream>
#include <fstream>
#include <algorithm>
#include <vector>
#include <cstring>

using namespace std;

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

const int MAXBIT = 5;//22;

struct Trie {
    Trie *son[2];
    int start;

    Trie() {
        memset(son, 0, sizeof son);
        start = -1;
    }
};

Trie *trie = new Trie;

int n, curXOR = 0;

void init (int poz, Trie *cur) {
    if (poz == -1) {
        cur->start = 1;
        return;
    }

    cur->son[0] = new Trie;
    init(poz - 1, cur->son[0]);
}

int test (int poz, int &best, int a, Trie *cur) {
    if (poz == -1) {
        return cur->start;
    }

    int bit = ((1 << poz) & a) != 0;
    bit = bit ^ ((curXOR & (1 << poz)) != 0);

    if (cur->son[1] == 0) {
        best += (1 << poz) * bit;
        return test (poz - 1, best, a, cur->son[0]);
    }
    else if (cur->son[0] == 0) {
        best += (1 << poz) * !bit;
        return test (poz - 1, best, a, cur->son[1]);
    }
    else {
        best += (1 << poz);
        return test (poz - 1, best, a, cur->son[!bit]);
    }
    return -1;
}

void adauga (int poz, int st, int a, Trie *cur) {
    if (poz == -1) {
        cur->start = st;
        return;
    }

    int bit = ((1 << poz) & a) != 0;

    int type = (curXOR & (1 << poz)) != 0;

    if (cur->son[type] == 0)
        cur->son[type] = new Trie;

    adauga (poz - 1, st, a, cur->son[type]);

    if (bit) curXOR ^= (1 << poz);
}

int main() {
    fin >> n;

    init(MAXBIT, trie);

    int bestst, bestfn, best = -1;
    for (int i = 1; i <= n; ++i) {
        int a; fin >> a;
        int curBest = 0, newstart;

        newstart = test(MAXBIT, curBest, a, trie);
        if (curBest > best) {
            best = curBest;
            bestst = newstart;
            bestfn = i;
        }
        adauga(MAXBIT, i, a, trie);
        adauga(MAXBIT, i + 1, 0, trie);

    }

    fout << best << " " << bestst << " " << bestfn << "\n";
    return 0;
}