Submission #1256565

#	Time	Username	Problem	Language	Result	Execution time	Memory
1256565		lechugon	XOR (IZhO12_xor)	C++20	100 / 100	82 ms	71752 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;
const int INF = 1e9 + 10;
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);
    }
}
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][num_bit ^ 1];
            if(opposite != -1)
                res = min(res, mxId[opposite]);
            node = trie[node][num_bit];
        }else 
            node = trie[node][num_bit ^ 1];
    }
    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 = -1;
    int idx = INF;
    if(k == 0) cout << 1 << ' ' << n << '\n';
    else{
        int pref = 0;
        for(int i = 0; i < n; i++){
            pref ^= a[i];
            if(pref >= k && i + 1 > ans) {
                ans = i + 1;
                idx = 0;
            }
            else{
                int id = query(pref , k);
                if(id != INF){
                    int res = i - id;
                    if(res > ans){
                        ans = max(ans, i - id);
                        idx = id + 1;
                    }
                }
            }
            insert(pref , i);
        }
        int val = 0;
        for(int i = idx; i <= idx + ans - 1; i++) val ^= a[i];
        assert(val >= k);
        cout << idx + 1 << ' ' << ans << '\n';
    }
}
int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    solve();
    return 0;
}

• Subtask 1: 100 / 100