Submission #547747

#	Time	Username	Problem	Language	Result	Execution time	Memory
547747		Deepesson	XOR (IZhO12_xor)	C++17	100 / 100	913 ms	18508 KiB

xor

#include <bits/stdc++.h>
#define MAX 8800000
#define LOGN 30
int filhos[MAX][2];
int cur=1;
int alocar(void){
    int x = cur++;
    filhos[x][0]=filhos[x][1]=0;
    return x;
}
int inicio;
void clear(void){cur=1;inicio=alocar();}
bool check(int B,int X){///Checar se existe A xor B MAIOR que X
    int base = inicio;
    for(int i=LOGN-1;i!=-1;--i){
        bool atual = (B&(1<<i));
        bool objet = (X&(1<<i));
        int prox=-1;
        for(int j=0;j!=2;++j){
            if(filhos[base][j]){
             ///   std::cout<<"Achou "<<j<<"\n";
                bool k = atual^j;
                ///Encontrou um valor MAIOR :)
                if(k>objet){
                    return true;
                }
                ///Encontrou um valor IGUAL
                if(k==objet)prox = filhos[base][j];
            }
        }
        ///Nao conseguiu manter o nivel
        if(prox==-1){///std::cout<<"Fracasso "<<atual<<" "<<objet<<"\n";
                return false;}
        base=prox;
    }
    ///Chegou no final e nao conseguiu aumentar nenhuma vez
    return false;
}

///Adiciona o inteiro A na lista
void catalogar(int A){
    int base=inicio;
    for(int i=LOGN-1;i!=-1;--i){
        bool valor = A&(1<<i);
        if(filhos[base][valor]){
            base=filhos[base][valor];
        }else base=filhos[base][valor]=alocar();
    }
}

int array[255000];
int N;
int tec=0;
bool tenta(int S,int obj){
    clear();
    int xoros[255000]={};
    xoros[0]=0;
    int xort = 0;
    for(int i=0;i!=N;++i){
        xort^=array[i];
        int p = i-S+1;
        xoros[i+1]=xort;
        if(p>=0)catalogar(xoros[p]);
        if(check(xort,obj-1)){
            tec=i-S+1;
            return true;
        }
    }
   /// std::cout<<"Xort final: "<<xort<<"\n";
    check(xort,obj-1);
    return false;
}

int main()
{
    std::ios::sync_with_stdio(false);
    std::cin.tie(0);
    std::cout.tie(0);

    int X;
    std::cin>>N>>X;
    int min=0;
    for(int i=0;i!=N;++i){
        std::cin>>array[i];
        if(array[i]>=X)min=1;
    }
    int l=0,r=N;
    while(l<r){
        int m = (l+r+1)/2;
        if(tenta(m,X)){
            l=m;
        }else {r=m-1;///std::cout<<"Falhou "<<m<<"\n";
        }
    }
    if(min>=l){
        for(int i=0;i!=N;++i){
            if(array[i]>=X){
                std::cout<<(i+1)<<" "<<1<<"\n";
                return 0;
            }
        }
    }
    tenta(l,X);
    std::cout<<(tec+1)<<" "<<std::max(min,l)<<"\n";
}

• Subtask 1: 100 / 100