Submission #1256509

#	Time	Username	Problem	Language	Result	Execution time	Memory
1256509		lechugon	XOR (IZhO12_xor)	C++20	0 / 100	32 ms	70720 KiB

xor

#include <bits/stdc++.h>
#define all(x) begin(x),end(x)
#define sz(x) (int)(x).size()
#define rep(i,a,b) for(int i = (a); i < (b); i++)
using namespace ::std;
using ll = long long;
typedef vector<int> vi;

const int N = 2e5 + 10;
const int SZ = N * 30 + 5;
const int LOG = 30;
int trie[SZ][2];
int mxId[SZ];
int ct;
void insert(int num , int id){
    int node = 0;
    for(int i = LOG; i >= 0; i--){
        int val = (num >> i) & 1;
        if(trie[node][val] == -1) trie[node][val] = ++ct;
        node = trie[node][val];
        mxId[node] = min(mxId[node] , id);
    }
}
const int INF = 3e5 + 10;
int query(int num, int k) {
    int node = 0;
    int res = INF;
    for(int i = LOG; i >= 0; i--){
        if(node == -1) break;        
        int num_bit = (num >> i) & 1;
        int k_bit = (k >> i) & 1;
        if(k_bit == 0){
            int opposite = trie[node][1 - num_bit];
            if(opposite != -1)
                res = min(res, mxId[opposite]);
            node = trie[node][num_bit];
        }else 
            node = trie[node][1 - num_bit];
    }
    if(node != -1)
        res = min(res, mxId[node]);
    return res;
}
void solve(){
    for(int i = 0; i < SZ; i++) mxId[i] = INF;
    memset(trie, -1 , sizeof trie);
    int n,k; cin >> n >> k;
    vi a(n); for(int i = 0 ; i < n; i++) cin >> a[i];
    int ans = INF;
    int idx = INF;
    if(k == 0) cout << 1 << '\n';
    else{
        int pref = 0;
        for(int i = 0; i < n; i++){
            pref ^= a[i];
            int id = query(pref , k);
            if(id != INF){
                int res = i - id + 1;
                // cerr << "I: " << i << '\n'; 
                // cerr << "ID: " << id << '\n';
                if(res < ans){
                    ans = min(ans, i - id);
                    idx = id + 1;
                }
            }
            insert(pref , i);
        }
        // if(ans == 1e9 + 10) ans = -1;
        cout << idx + 1 << ' ' << ans << '\n';
    }
}
int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    solve();
    return 0;
}

• Subtask 1: 0 / 100