Cod sursa(job #2660735)

Utilizator Dobricean_IoanDobricean Ionut Dobricean_Ioan Data 20 octombrie 2020 13:16:04
Problema Xor Max Scor 50
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.91 kb
#include <fstream>
#include <cstring>

using namespace std;

ifstream cin("xormax.in");
ofstream cout("xormax.out");

int p[23],n,v[100001],maxi,y,z1,z2,nr;
bool s[23];

struct Trie {
	Trie *Bit[26];
	int prefix,cuv,numar;
	Trie(){
        for(short int i=0;i<26;i++)
            Bit[i]=nullptr;
            prefix=0;
            cuv=0;
    }
};


Trie *rad =new Trie();

void ADD(Trie *&nod, int i, int dr) {
    if (i == 22) {
        nod -> numar = dr;
        return;
    }
    if(nod -> Bit[s[i]] == NULL) {
        nod -> Bit[s[i]] = new Trie;
    }
    ADD(nod -> Bit[s[i]], i + 1,dr);
    return;
}
void REMOVE(  char  *x){
    Trie *aux=rad;
    for(short int i=0;i<strlen(x);i++){
        if(aux->Bit[x[i]-'a']==nullptr) {
			return;
        }
        aux->Bit[x[i]-'a']->prefix--;
        aux=aux->Bit[x[i]-'a'];
    }
    aux->cuv--;
}
void CHANGE(int x)  {
    int k = -1;
    for (int i = 0; i <= 21; i ++) {
        s[i] = 0;
    }
    while (x > 0) {
        s[++k] = x % 2;
        x /= 2;
    }
    for (int i = 0; i <= 10; i ++) {
        swap (s[i],s[21-i]);
    }
    return;
}
int dfs(Trie *&nod,int i) {
    if (i==22) {
        y=nod->numar;
        return 0;
    }
    if (nod->Bit[1-s[i]]!=NULL) {
        return p[(21-i)]+dfs(nod->Bit[1-s[i]],i+1);
    }
    else {
        return dfs(nod->Bit[s[i]],i+1);
    }

}


int main (void) {
    cin>>n;
    for(int i=1;i<=n;i++) {
        cin>>v[i];
    }
    for(int i=1;i<=n;i++) {
        v[i]=(v[i] ^ v[i-1]);
    }
    p[0]=1;
    for(int i=1;i<=22;i++) {
        p[i]=p[i-1]*2;
    }
    maxi=-1;
    CHANGE(0);
    ADD(rad,0,0);
    for(int i=1;i<=n;i++) {
        CHANGE(v[i]);
        nr=dfs(rad,0);
        if(nr>maxi) {
            maxi=nr;
            z1=i;
            z2=y;
        }
        ADD(rad,0,i);
    }
    cout<<maxi<<" "<<z2+1<<" "<<z1<<" ";
    return 0;
}