Submission #547750

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
547750	2022-04-11T15:07:49 Z	Deepesson	XOR (IZhO12_xor)	C++17	100 / 100	953 ms	16852 KB

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.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	36 ms	1856 KB	Output is correct
6	Correct	42 ms	1876 KB	Output is correct
7	Correct	49 ms	1876 KB	Output is correct
8	Correct	54 ms	2032 KB	Output is correct
9	Correct	245 ms	8704 KB	Output is correct
10	Correct	253 ms	8760 KB	Output is correct
11	Correct	245 ms	8604 KB	Output is correct
12	Correct	248 ms	8816 KB	Output is correct
13	Correct	241 ms	8732 KB	Output is correct
14	Correct	248 ms	8792 KB	Output is correct
15	Correct	258 ms	8756 KB	Output is correct
16	Correct	237 ms	8692 KB	Output is correct
17	Correct	859 ms	16704 KB	Output is correct
18	Correct	857 ms	16852 KB	Output is correct
19	Correct	953 ms	16776 KB	Output is correct
20	Correct	821 ms	16716 KB	Output is correct