Cod sursa(job #2188035)

Utilizator ciprianprohozescuProhozescu Ciprian ciprianprohozescu Data 26 martie 2018 21:46:13
Problema Xor Max Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 3.01 kb
#include <fstream>
#include <vector>
#include <algorithm>
#define NMAX 100010
#define PMAX 21

using namespace std;

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

struct trie
{
    trie *fiu[2];
    vector<int> poz;

    trie()
    {
        fiu[0] = fiu[1] = 0;
    }
};
struct solutie
{
    int s, st, dr;
};

int n, v[NMAX];
trie *t = new trie;
solutie sol;

void inserare(trie *nod, int k, int x, int i);
void cautare(trie *a, trie *b, int k, int s);
void cautare_interval(vector<int> a, vector<int> b);

int main()
{
    int i, x;
    fin >> n;
    for (i = 1; i <= n; i++)
    {
        fin >> x;
        v[i] = v[i - 1] ^ x;
        inserare(t, (1 << PMAX), v[i], i);
    }
    sol.dr = n + 5;
    cautare(t, t, (1 << PMAX), 0);
    fout << sol.s << ' ' << sol.st << ' ' << sol.dr << '\n';
    fout.close();
    return 0;
}

void inserare(trie *nod, int k, int x, int i)
{
    if (!k)
    {
        nod->poz.push_back(i);
        return ;
    }
    if (nod->fiu[(x & k) || 0] == 0)
        nod->fiu[(x & k) || 0] = new trie;
    inserare(nod->fiu[(x & k) || 0], (k >> 1), x, i);
}
void cautare(trie *a, trie *b, int k, int s)
{
    if (!k)
    {
        if (s >= sol.s)
        {
            if (s > sol.s)
            {
                sol.st = 0;
                sol.dr = 10;
            }
            sol.s = s;
            cautare_interval(a->poz, b->poz);
        }
        return ;
    }
    if (a->fiu[0])
    {
        if (b->fiu[1])
        {
            cautare(a->fiu[0], b->fiu[1], (k >> 1), s + k);
            if (a->fiu[1] && b->fiu[0])
                cautare(a->fiu[1], b->fiu[0], (k >> 1), s + k);
        }
        else
        {
            if (b->fiu[0])
                cautare(a->fiu[0], b->fiu[0], (k >> 1), s);
            if (a->fiu[1] && b->fiu[1])
                cautare(a->fiu[1], b->fiu[1], (k >> 1), s);
        }
    }
    else if (a->fiu[1])
    {
        if (b->fiu[0])
            cautare(a->fiu[1], b->fiu[0], (k >> 1), s + k);
        else if (b->fiu[1])
            cautare(a->fiu[1], b->fiu[1], (k >> 1), s);
    }
}
void cautare_interval(vector<int> a, vector<int> b)
{
    int i, j;
    for (i = 0; i < a.size() && a[i] <= sol.dr; i++)
    {
        j = lower_bound(b.begin(), b.end(), a[i]) - b.begin();
        if (j == b.size())
            j--;
        if (b[j] < a[i])
        {
            if (a[i] < sol.dr || (a[i] == sol.dr && a[i] - (b[j] + 1) < sol.dr - sol.st))
            {
                sol.st = b[j] + 1;
                sol.dr = a[i];
            }
        }
    }
    for (i = 0; i < b.size() && b[i] <= sol.dr; i++)
    {
        j = lower_bound(a.begin(), a.end(), b[i]) - a.begin();
        if (j == a.size())
            j--;
        if (a[j] < b[i])
        {
            if (b[i] < sol.dr || (b[i] == sol.dr && b[i] - (a[j] + 1) < sol.dr - sol.st))
            {
                sol.st = a[j] + 1;
                sol.dr = b[i];
            }
        }
    }
}