Cod sursa(job #2533307)

Utilizator AlexPascu007Pascu Ionut Alexandru AlexPascu007 Data 28 ianuarie 2020 21:33:41
Problema Xor Max Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.46 kb
#include <bits/stdc++.h>
#define DIM 100010
using namespace std;
ifstream fin("xormax.in");
ofstream fout("xormax.out");
int n,i,x,maxx,nr,maxim,st,dr,solpoz,s[DIM];
struct trie{
    int poz;
    trie *f[2];
    trie() {
        f[0]=f[1]=0;
        poz=0;
    }
};
trie *r;
void insertTrie(trie *r, int bit,int val,int poz) {
    if (bit==-1) {
        r->poz=poz;
        return;
    }
    if (((val>>bit)&1)==0) {
        if (r->f[0]==nullptr)
            r->f[0]=new trie();
        insertTrie(r->f[0],bit-1,val,poz);
    }
    else {
        if (r->f[1]==nullptr)
            r->f[1]=new trie();
        insertTrie(r->f[1],bit-1,val,poz);
    }
}
void searchTrie(trie *r,int bit,int val) {
    if (bit==-1) {
        solpoz=r->poz;
        return;
    }
    int bitval=((val>>bit)&1);
    if (r->f[1-bitval]!=0)
        searchTrie(r->f[1-bitval],bit-1,val);
    else
        searchTrie(r->f[bitval],bit-1,val);
}
int main() {
    fin>>n>>s[1];
    maxim=-1;
    for (i=2;i<=n;i++) {
        fin>>x;
        if (x>maxx)
            maxx=x;
        s[i]=(x^s[i-1]);
    }
    while (maxx)
        nr++, maxx/=2;
    r=new trie();
    insertTrie(r,nr,0,0);
    for (i=1;i<=n;i++) {
        searchTrie(r,nr,s[i]);
        if ((s[i]^s[solpoz])>maxim) {
            maxim=(s[i]^s[solpoz]);
            st=solpoz+1;
            dr=i;
        }
        insertTrie(r,nr,s[i],i);
    }
    fout<<maxim<<" "<<st<<" "<<dr;
    return 0;
}