Cod sursa(job #1960192)

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

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

const int NMax = 2200005;
const int BitMax = 24;

struct Trie{
    int sons[2];
};

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

int n,mx = -1,ind,ans2,ans3;
int a[NMax],x[NMax],v[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;
        int ans = 0;
        for(int j = nr; j >= 1; --j){
            if(T[node].sons[1 - v[j]]){
                ans = ans * 2 + 1;
                node = T[node].sons[1 - v[j]];
            }else{
                ans = ans * 2;
                node =  T[node].sons[v[j]];
            }
        }


        if(ans > mx){
            ind = i;
            mx = ans;
        }

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

    g << mx << ' ';

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

    return 0;
}