Submission #547742

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
547742	2022-04-11T14:51:41 Z	Deepesson	XOR (IZhO12_xor)	C++17	0 / 100	1 ms	1236 KB

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=0;i!=LOGN;++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]){
                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)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=0;i!=LOGN;++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;
        xoros[i]=xort;
        if(p>=0)catalogar(xoros[p]);
        if(check(xort,obj-1)){
            tec=i-S+1;
            return true;
        }
    }
    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;
    }
    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

0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Incorrect	1 ms	1236 KB	Output isn't correct
2	Halted	0 ms	0 KB	-