Cod sursa(job #1110281)

Utilizator deneoAdrian Craciun deneo Data 17 februarie 2014 22:02:54
Problema Xor Max Scor 15
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.88 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 = 22;

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

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

Trie *trie = new Trie;

int n;

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;

    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;

    if (bit) swap (cur->son[0], cur->son[1]);

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

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

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);

    }

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