Cod sursa(job #807211)

Utilizator dicu_dariaDaria Dicu dicu_daria Data 4 noiembrie 2012 13:17:32
Problema Xor Max Scor 40
Compilator cpp Status done
Runda 00001 Marime 1.75 kb
#include <iostream>
#include <fstream>

using namespace std;

int i, s[100010], j, x, a, n, step, stop, maxstop, maxstart, maxim, sum;
bool t[30];
struct Trie{
    Trie *fiu[2];
    int poz;
    Trie()
    {
        poz = 0;
        fiu[0] = fiu[1] = 0;
    }
};
Trie *T = new Trie;
void adauga(Trie *node, int p)
{
    if(p > 21)
    {
        if(!node->poz) node->poz = i;
        return;
    }
    if(!node->fiu[t[p]])
        node->fiu[t[p]] = new Trie();
    adauga(node->fiu[t[p]], p+1);
}
int get_max(Trie *node, int p, int bit)
{
    if(p > 21)
    {
        stop = node->poz;
        return 0;
    }
    if(node->fiu[1-t[p]])
        return get_max(node->fiu[1-t[p]], p+1, bit >> 1)+bit;
    else
        return get_max(node->fiu[t[p]], p+1, bit >> 1);
}
int main()
{
    ifstream fi("xormax.in");
    ofstream fo("xormax.out");
    fi >> n;
    fi >> s[1];
    for(i = 2; i <= n; i++)
    {
        fi >> a;
        s[i] = s[i-1]^a;
    }
    for(i = n; i >= 1; i--)
    {
        for(step = 1, j = 1; j <= 20; j++, step <<= 1);
        for(j = 1; j <= 21; step >>= 1, j++)
            if(step&s[i]) t[j] = 1; else t[j] = 0;

        for(step = 1, j = 1; j <= 20; j++, step <<= 1);
        if(i != n)
        {
            sum = get_max(T, 1, step);
            if(sum > maxim or (sum == maxim and stop < maxstop))
            {
                maxim = sum;
                maxstop = stop;
                maxstart = i+1;
            }
        }
        adauga(T, 1);
    }
    for(i = 1; i <= n; i++)
    if(s[i] > maxim or (s[i] == maxim and i == maxstop and maxstop-maxstart+1 > i) or (s[i] == maxim and i < maxstop))
    {
        maxim = s[i];
        maxstop = i;
        maxstart = 1;
    }
    fo << maxim << " " << maxstart << " " << maxstop << "\n";
    return 0;
}