Submission #1164937

#	Time	Username	Problem	Language	Result	Execution time	Memory
1164937		LmaoLmao	XOR (IZhO12_xor)	C++20	100 / 100	69 ms	21320 KiB

xor

#include<bits/stdc++.h>
#define fi first
#define se second
//#define int long long
using namespace std;

using ll = long long;
using ii = pair<ll, ll>;
using aa = array<int,4>;

const int N = 1e6+5;
const int INF = 1e9;
const int MOD = 1e5+3;

int trie[10000005][2];
int a[10000005];
int timer=0;

int get(int x,int k) {
    int u=0;
    int res=1e6;
    for(int i=30;i>=0;i--) {
        int vx=(x >> i) & 1,vk=(k >> i) & 1;
        if(vx && vk) {
            if(!trie[u][0]) return res;
            u=trie[u][0];
        } else
        if(vx && !vk) {
            if(trie[u][0]) res=min(res,a[trie[u][0]]);
            if(!trie[u][1]) return res;
            u=trie[u][1];
        }else 
        if(!vx && vk) {
            if(!trie[u][1]) return res;
            u=trie[u][1];
        }
        else {
          if(trie[u][1]) res=min(res,a[trie[u][1]]);
          if(!trie[u][0]) return res;
          u=trie[u][0];
        }
    }
    res=min(res,a[u]);
    return res;
}

void add(int x,int val) {
    int u=0;
    for(int i=30;i>=0;i--) {
        int v=(x >> i) & 1;
        if(!trie[u][v]) {
            trie[u][v]=++timer;
            a[timer]=val;
        }
        u=trie[u][v];
        a[u]=min(a[u],val);
    }
}

signed main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); 
    int n,k;
    cin >> n >> k;
    int sum=0;
    ii ans={0,0};
    add(sum,0);
    for(int i=1;i<=n;i++) {
        int x;
        cin >> x;
        sum ^= x;
        int t=get(sum,k);
        if(i-t>ans.se) {
            ans={t+1,i-t};
        }
        //cout << sum << ' ' << t << ' ' << ans.se << endl;
        //cout << get(sum,k) << ' ' << sum << endl;
        add(sum,i);
    }
    cout << ans.fi << ' ' << ans.se;
    return 0;
}
 
/*
██╗░░██╗██╗░░██╗░█████╗░███╗░░██╗░██████╗░              ░██████╗██╗██╗░░░██╗                ░█████╗░██╗░░░██╗████████╗███████╗
██║░██╔╝██║░░██║██╔══██╗████╗░██║██╔════╝░              ██╔════╝██║██║░░░██║                ██╔══██╗██║░░░██║╚══██╔══╝██╔════╝
█████═╝░███████║███████║██╔██╗██║██║░░██╗░              ╚█████╗░██║██║░░░██║                ██║░░╚═╝██║░░░██║░░░██║░░░█████╗░░
██╔═██╗░██╔══██║██╔══██║██║╚████║██║░░╚██╗              ░╚═══██╗██║██║░░░██║                ██║░░██╗██║░░░██║░░░██║░░░██╔══╝░░
██║░╚██╗██║░░██║██║░░██║██║░╚███║╚██████╔╝              ██████╔╝██║╚██████╔╝                ╚█████╔╝╚██████╔╝░░░██║░░░███████╗
╚═╝░░╚═╝╚═╝░░╚═╝╚═╝░░╚═╝╚═╝░░╚══╝░╚═════╝░              ╚═════╝░╚═╝░╚═════╝░                ░╚════╝░░╚═════╝░░░░╚═╝░░░╚══════╝
*/

• Subtask 1: 100 / 100