Cod sursa(job #2679340)

Utilizator WladDalwMvladutu cristian vlad WladDalwM Data 30 noiembrie 2020 12:50:43
Problema Xor Max Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.54 kb
#include <bits/stdc++.h>

using namespace std;

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

int d[100005];

int i;

struct Trie
{
    int nr;
    Trie *fiu[2];
    Trie(){fiu[0] = fiu[1] = 0;nr = 0;}
};

Trie *root;

void insert(Trie *trie, int b , int nr)
{
    if(b == -1)
        {trie->nr = i;return;}
    bool x = nr&(1<<b);
    if(trie->fiu[x] == NULL)
        trie->fiu[x] = new Trie;
    insert(trie->fiu[x] , b - 1 , nr);
}

int search(Trie *trie, int b , int nr)
{
    if(b == -1)
        return trie->nr;
    bool x = nr&(1<<b);
    if(trie->fiu[1-x] != NULL)
        return search(trie->fiu[1-x] , b - 1, nr);
    return search(trie->fiu[x] , b - 1 , nr);
}

int main()
{
    int n;
    int maxim = 0;
    int rezj , rezi;
    in >> n;
    root = new Trie;
    insert(root , 20 , 0);
    for(i = 1; i <= n; ++i)
    {
        int a;
        in >> a;
        d[i] = (a ^ d[i - 1]);
        int j = search(root , 20 , d[i]);
        if((d[i] ^ d[j]) > maxim)
        {
            rezi = i;
            rezj = j + 1;
            maxim = (d[i] ^ d[j]);
        }
        else
        if((d[i] ^ d[j]) == maxim)
        {
            if(i < rezi)
            {
                rezi = i;
                rezj = j + 1;
            }
            else
            if(i == rezi)
            {
                if(j + 1 > rezj)
                    rezj = j + 1;
            }
        }
        insert(root , 20 , d[i]);
    }
    out << maxim << " " << rezj << " " <<rezi;
    return 0;
}