Submission #966125

#	Time	Username	Problem	Language	Result	Execution time	Memory
966125		noyancanturk	XOR (IZhO12_xor)	C++17	100 / 100	123 ms	178520 KiB

xor

#include "bits/stdc++.h"
using namespace std;
    
//#define int int64_t
#define pb push_back
    
const int lim=1.5e7+500;
const int mod=1e9+7;

using pii=pair<int,int>;

int n,k;

struct{
    
    struct node{
        int c[2];
        int val=INT_MAX;
    };

    node nds[lim];
    int cnd=2;

    #define now nds[cur]

    void insert(int x,int k){
        int cur=1;
        for(int i=29;0<=i;i--){
            if(!now.c[(x>>i)&1]){
                now.c[(x>>i)&1]=cnd++;
            }
            cur=now.c[(x>>i)&1];
            if(k<now.val)now.val=k;
        }
    }

    int findval(int x){
        int ans=INT_MAX,cur=1;
        for(int i=29;0<=i;i--){
            bool bt=(x>>i)&1;
            if((k>>i)&1){
                if(!now.c[!bt]){
                    return ans;
                }
                cur=now.c[!bt];
            }else{
                if(now.c[!bt]&&nds[now.c[!bt]].val<ans){
                    ans=nds[now.c[!bt]].val;
                }
                if(!now.c[bt]){
                    return ans;
                }
                cur=now.c[bt];
            }
        }
        return min(ans,now.val);
    }

}trie;

signed main(){
    ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#ifdef Local  
    freopen(".in","r",stdin); freopen(".out","w",stdout);
#endif
    cin>>n>>k;
    int past=0;
    int64_t l=0,r=-1,sz=0;
    trie.insert(0,-1);
    for(int i=0;i<n;i++){
        int tem;
        cin>>tem;
        past^=tem;
        int ll=trie.findval(past);
        if(ll!=INT_MAX&&sz<i-ll){
            l=ll+1;
            sz=i-ll;
        }
        trie.insert(past,i);
    }
    cout<<l+1<<" "<<sz<<"\n";
}

Compilation message (stderr)

xor.cpp: In function 'int main()':
xor.cpp:68:17: warning: unused variable 'r' [-Wunused-variable]
   68 |     int64_t l=0,r=-1,sz=0;
      |                 ^

• Subtask 1: 100 / 100