제출 #547750

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
547750		Deepesson	XOR (IZhO12_xor)	C++17	100 / 100	953 ms	16852 KiB

xor

#include <bits/stdc++.h>
#define MAX 8800000
#define LOGN 30
int sons[MAX][2];
int cur=1;
///Get a new trie node
int aloc(void){
    int x = cur++;
    sons[x][0]=sons[x][1]=0;
    return x;
}
///First node of the trie
int start;
///Clear the trie
void clear(void){cur=1;start=aloc();}

bool check(int B,int X){///Checking if there's some A xor B BIGGER than X
    int base = start;
    for(int i=LOGN-1;i!=-1;--i){
        bool now = (B&(1<<i));
        bool objective = (X&(1<<i));
        int prox=-1;
        for(int j=0;j!=2;++j){
            if(sons[base][j]){
                bool k = now^j;
                ///We found a bigger value :)
                if(k>objective){
                    return true;
                }
                ///We found the same value
                if(k==objective)prox = sons[base][j];
            }
        }
        ///We didn't find any value in the same level
        if(prox==-1)
        {
            return false;
        }
        base=prox;
    }
    ///We reached the end without finding any bigger value
    return false;
}

///Add an integer A in the XOR list
void add_value(int A){
    int base=start;
    for(int i=LOGN-1;i!=-1;--i){
        bool valor = A&(1<<i);
        if(sons[base][valor]){
            base=sons[base][valor];
        }else base=sons[base][valor]=aloc();
    }
}

int array[255000];
int N;
int tec=0;
///Can we solve the problem with segments of size S? (While X = obj)
bool try_size(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)add_value(xoros[p]);
        if(check(xort,obj-1)){
            tec=i-S+1;
            return true;
        }
    }
    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;
    }
    ///Check if we can solve the problem with segments of size M or bigger
    int l=0,r=N;
    while(l<r){
        int m = (l+r+1)/2;
        if(try_size(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;
            }
        }
    }
    try_size(l,X);
    std::cout<<(tec+1)<<" "<<std::max(min,l)<<"\n";
}

• Subtask 1: 100 / 100