Submission #1275931

#	Time	Username	Problem	Language	Result	Execution time	Memory
1275931		anarch_y	XOR (IZhO12_xor)	C++20	100 / 100	113 ms	25268 KiB

xor

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define all(x) begin(x), end(x)
#define sz(x) (int)x.size()
#define pb push_back

struct Trie{
    static const int wmax = 6e6+1;
    int trie[wmax][2];
    int mn[wmax];
    bool stop[wmax];
    int num;
 
    void insert(int x, int j){
        int cur = 0;
        for(int i=30; i>=0; i--){
            bool c = x & (1<<i);
            if(trie[cur][c] == 0){
                trie[cur][c] = ++num;
            }
            cur = trie[cur][c];
        }
        if(!stop[cur]){
            stop[cur] = true;
            mn[cur] = j;
        }
    }

    void dfs(int cur){
        if(stop[cur]) return;
        mn[cur] = 1e9;
        for(int c=0; c<2; c++){
            if(trie[cur][c]){
                dfs(trie[cur][c]);
                mn[cur] = min(mn[cur], mn[trie[cur][c]]);
            }
        }
    }

    int find(int m, int x){
        int cur = 0;
        int ans = 1e9;
        for(int i=30; i>=0; i--){
            bool c = m & (1<<i);
            bool d = x & (1<<i);
            if(c == 0){
                if(d == 0){
                    if(trie[cur][1]){
                        ans = min(ans, mn[trie[cur][1]]);
                    }
                    if(trie[cur][0]) cur = trie[cur][0];
                    else break;
                }
                else{
                    if(trie[cur][1]) cur = trie[cur][1];
                    else break;
                }
            }
            else{
                if(d == 0){
                    if(trie[cur][0]){
                        ans = min(ans, mn[trie[cur][0]]);
                    }
                    if(trie[cur][1]) cur = trie[cur][1];
                    else break;
                }
                else{
                    if(trie[cur][0]) cur = trie[cur][0];
                    else break;
                }
            }
        }
        return ans;
    }
};

Trie T;

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);

    int n, x; cin >> n >> x;
    vector<int> a(n+1);
    for(int i=1; i<=n; i++) cin >> a[i];
    if(x == 0){
        cout << 1 << ' ' << n;
        return 0;
    }
    x--;
    vector<int> p(n+1);
    T.insert(0, 0);
    for(int i=1; i<=n; i++){
        p[i] = (a[i]^p[i-1]);
        T.insert(p[i], i);
    }
    T.dfs(0);
    int k = 0;
    for(int i=1; i<=n; i++){
        int j = T.find(p[i], x);
        if(j < i){
            k = max(k, i-j);
        }
    }
    for(int i=1; i+k-1<=n; i++){
        if((p[i+k-1]^p[i-1]) > x){
            cout << i << ' ' << k;
            return 0;
        }
    }
}

• Subtask 1: 100 / 100