Submission #547747

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
547747	2022-04-11T15:02:06 Z	Deepesson	XOR (IZhO12_xor)	C++17	100 / 100	913 ms	18508 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=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.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	1236 KB	Output is correct
2	Correct	1 ms	1236 KB	Output is correct
3	Correct	1 ms	1236 KB	Output is correct
4	Correct	3 ms	1364 KB	Output is correct
5	Correct	37 ms	1752 KB	Output is correct
6	Correct	43 ms	1748 KB	Output is correct
7	Correct	49 ms	1832 KB	Output is correct
8	Correct	54 ms	1748 KB	Output is correct
9	Correct	248 ms	8320 KB	Output is correct
10	Correct	249 ms	9144 KB	Output is correct
11	Correct	251 ms	9092 KB	Output is correct
12	Correct	250 ms	9016 KB	Output is correct
13	Correct	256 ms	9228 KB	Output is correct
14	Correct	247 ms	9032 KB	Output is correct
15	Correct	251 ms	9108 KB	Output is correct
16	Correct	241 ms	9104 KB	Output is correct
17	Correct	890 ms	18304 KB	Output is correct
18	Correct	913 ms	18212 KB	Output is correct
19	Correct	900 ms	18352 KB	Output is correct
20	Correct	843 ms	18508 KB	Output is correct