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
#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";
}
# 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