Cod sursa(job #3187574)

Utilizator emazareMazare Emanuel emazare Data 29 decembrie 2023 16:14:16
Problema Xor Max Scor 20
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.66 kb
#include <fstream>

using namespace std;

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

const int N = 100005;
int nr;
struct trie{
    trie *leg[2];
    int val;
    trie(){
        leg[0] = nullptr;
        leg[1] = nullptr;
        val = 0;
    }
};
struct solution{
    int val;
    int step;
} dp[N];
trie *root = new trie;

void add(trie *node, int pos, int step){
    if(pos == -1){
        node->val = step;
        return;
    }
    int ch = nr&(1<<pos);
    if(ch>0)
        ch = 1;
    if(!node->leg[ch])
        node->leg[ch] = new trie;
    node->val = step;
    add(node->leg[ch],pos-1,step);
}
solution xormax(trie *node, int pos){
    solution sol;
    if(pos == -1){
        sol.val = 0;
        sol.step = node->val;
        return sol;
    }
    int ch = nr&(1<<pos);
    if(ch>0)
        ch = 1;
    if(node->leg[1-ch]){
        sol.val = (1<<pos)+xormax(node->leg[1-ch],pos-1).val;
        sol.step = xormax(node->leg[1-ch],pos-1).step;
        return sol;
    }
    else{
        sol.val = xormax(node->leg[ch],pos-1).val;
        sol.step = xormax(node->leg[ch],pos-1).step;
        return sol;
    }
}

int main()
{
    int n,i,xr,nmax = 0,ind = 0;
    fin >> n;
    xr = 0;
    dp[0].val = 0; dp[0].step = 0;
    nr = 0; add(root,20,0);
    for(i=1;i<=n;i++){
        fin >> nr;
        nr^=xr;
        xr = nr;
        dp[i] = xormax(root,20);
        add(root,20,i);
    }
    for(i=1;i<=n;i++)
        nmax = max(nmax,dp[i].val);
    for(i=n;i>0;i--){
        if(dp[i].val == nmax)
            ind = i;
    }
    fout << nmax << " " << dp[ind].step+1 << " " << ind;
    return 0;
}