Cod sursa(job #3169932)

Utilizator Radu_MocanasuMocanasu Radu Radu_Mocanasu Data 16 noiembrie 2023 12:51:30
Problema Xor Max Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.43 kb
#include <bits/stdc++.h>
#define p 20
using namespace std;
ifstream fin("xormax.in");
ofstream fout("xormax.out");
struct trie{
    int n;
    trie *f[2];
    trie(){
        n = 0;
        memset(f,0,sizeof f);
    }
};
trie *rad = new trie;
int ptemp;
void ins(int x, int cnt, trie *nod, int i){
    if(cnt < 0){
        nod->n = i;
        return;
    }
    int val;
    if((1 << cnt) & x) val = 1;
    else val = 0;
    if(nod->f[val] == 0){
        nod->f[val] = new trie;
    }
    ins(x,cnt - 1,nod->f[val],i);
}
int query(int x, int cnt, trie *nod){
    int res = 0;
    while(cnt >= 0){
        int val = ((1 << cnt) & x) ? 1 : 0;
        if(nod->f[!val] != 0){
            if(val == 0) res |= (1 << cnt);
            nod = nod->f[!val];
        }
        else{
            if(val == 1) res |= (1 << cnt);
            nod = nod->f[val];
        }
        cnt--;
    }
    ptemp = nod->n;
    return res;
}
int main()
{
    int n,i,x,sp = 0,q,m = -1,p1,p2;
    fin >> n;
    ins(0,p,rad,1);
    for(i = 1; i <= n; i++){
        fin >> x;
        sp ^= x;
        q = query(sp,p,rad);
        if((sp ^ q) > m){
            m = sp ^ q;
            p1 = ptemp;
            p2 = i;
        }
        ins(sp,p,rad,i + 1);
    }
    q = query(sp,p,rad);
    if((x ^ q) > m){
        m = x ^ q;
        p1 = ptemp;
        p2 = n;
    }
    fout << m << " " << p1 << " " << p2;
    return 0;
}