Cod sursa(job #1960136)

Utilizator VladTiberiuMihailescu Vlad Tiberiu VladTiberiu Data 10 aprilie 2017 11:12:00
Problema Xor Max Scor 35
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.63 kb
#include <bits/stdc++.h>

using namespace std;
ifstream f("xormax.in");
ofstream g("xormax.out");

const int NMax = 100001;
const int BitMax = 22;

struct Trie{
    int sons[2];
};

Trie T[NMax * 2];
int Size = 0;

int n,mx,ind;
int a[NMax],x[NMax],v[NMax];
vector<int> e[NMax];

int main()
{
    f >> n;
    for(int i = 1; i <= n; ++i){
        f >> a[i];
        if(i == 1)
            x[i] = a[i];
        else
            x[i] = x[i - 1] ^ a[i];
    }
    for(int i = 0; i <= n; ++i){
        int aux = x[i],nr = 0;
        while(aux){
            v[++nr] = aux % 2;
            aux /= 2;
        }
        while(nr < BitMax){
            v[++nr] = 0;
        }

        ///adaug in trie

        int node = 0;
        for(int j = nr; j >= 1; --j){
            e[i].push_back(v[j]);
            int next = T[node].sons[v[j]];
            if(next == 0){
                next = ++Size;
                T[node].sons[v[j]] = next;
            }
            node = next;
        }

        node = 0;
        int ans = 0;
        for(int j = 0; j < e[i].size(); ++j){
            if(T[node].sons[1 - e[i][j]]){
                ans = ans * 2 + 1;
                node = T[node].sons[1 - e[i][j]];
            }else{
                ans = ans * 2;
                node =  T[node].sons[e[i][j]];
            }
        }
        if(ans > mx){
            ind = i;
            mx = ans;
        }
    }

    g << mx << ' ';

    for(int i = 1; i <= n; ++i){
        if((x[i] ^ x[ind]) == mx){
            g << i + 1 << ' ' << ind << '\n';
            return 0;
        }
    }

    return 0;
}