제출 #1326759

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1326759		wafaa	XOR (IZhO12_xor)	C++20	0 / 100	0 ms	332 KiB

xor

#include <bits/stdc++.h>
#define Lol ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define ll long long
#define all(v) v.begin(),v.end()
#define rall(v) v.rbegin(),v.rend()
#define el <<'\n' ;
#define sz(s) (int)s.size()
using namespace std;
#define int ll
#define lint __int64
int dx[] = {1, -1, 0, 0};
int dy[] = {0, 0, 1, -1};
int inf = 1e6 ;
struct node {
    int nxt[2]{} , mn = inf;
    int &operator[](int b){
    return nxt[b] ;
    }
};
struct trie {
    vector<node> t;
    int new_node() {
        t.push_back(node()) ;
        return t.size() - 1 ;
    }
    trie() {
        new_node() ;
    }
    void insert(int x, int i) {
        int u = 0 , ok = 0 ;
        for (int bit = 31; bit >= 0 ; --bit) {
            int b = x >> bit & 1 ;
            if (b) ok = 1 ;
            if (!t[u][b]) {
                t[u][b] = new_node() ;
            }
            u = t[u][b] ;
            if (ok)
                t[u].mn = min(i, t[u].mn) ;
        }
    }

    int query(int pre, int x) {
        int u = 0 , ans = inf;
        for (int bit = 31; bit >= 0 ; --bit) {
            int bx = x >> bit & 1 , bpre = pre >> bit & 1;
            if (!bx) {
                ans = min(ans, t[t[u][bpre ^ 1]].mn ) ;
            }
            if (t[u][bx ^ bpre]){
                u = t[u][bx ^ bpre] ;
            }
            else {
                return ans;
            }
        }
        return ans ;
    }
};
void Tatakai() {
    int n , x; cin>>n>>x ;
    vector<int>v(n) ;
    for (auto &i : v) cin>>i ;
    int pre = 0 , idx = 1 , cur = 0 , l = -1 ;
    trie t ;
    for (auto i : v) {
        pre ^= i;
        if (pre >= x and cur < idx) {
            cur = idx , l = 1 ;
        }
        int ret = t.query(pre, x) ;
        if (ret < inf and cur < idx - ret) {
            l = ret + 1, cur = idx - ret ;
        }
        // cout<<pre<<' '<<ret<<' '<<cur<<endl;
        t.insert(pre, idx++) ;
    }
    cout<<l<<' '<<cur ;
}
int32_t main() {
    Lol
    int t = 1;
    // cin >> t;
    for (int i = 1; i <= t; ++i) {
        Tatakai();
        if (i < t)
            cout el
    }
    return 0;
}
/* practice makes PERFECT */

• Subtask 1: 0 / 100