제출 #1256530

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1256530		lechugon	XOR (IZhO12_xor)	C++20	0 / 100	35 ms	70728 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 << ' ' << 1 << '\n';
    // else{n
    insert(0 , -1);
    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 = max(ans, i - id);
                idx = id + 1;
            }
        }
        insert(pref , i);
    }
    // if(pref >= k) {idx = 1 ; k = n;}
    // 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