Submission #1107623

#	Time	Username	Problem	Language	Result	Execution time	Memory
1107623		Irate	XOR (IZhO12_xor)	C++17	100 / 100	141 ms	92328 KiB

xor

#include<bits/stdc++.h>
using namespace std;
struct Trie{
    vector<vector<int>>trie;
    vector<int>mn;
    int nxt = 1;
    Trie(int n){
        trie.resize(2);
        for(int i = 0;i < 2;++i){
            trie[i].resize(n + 1);
        }
        mn.resize(n, 1e9);
    }
    void Update(int val, int indx){
        int node = 0;
        for(int i = 30;i >= 0;--i){
            int bit = ((val >> i) & 1);
            if(trie[bit][node]){
                node = trie[bit][node];
                mn[node] = min(mn[node], indx);
            }
            else{
                node = trie[bit][node] = nxt++;
                mn[node] = min(mn[node], indx);
            }
        }
    }
    int Get(int val, int x){
        int node = 0, res = 1e9;
        bool flag = 1;
        for(int i = 30;i >= 0;--i){
            int bit_pref = ((val >> i) & 1), bit_x = ((x >> i) & 1);
            if(bit_pref && bit_x){
                if(trie[0][node]){
                    node = trie[0][node];
                }
                else{
                    flag = 0;
                    break;
                }
            }
            else if(bit_pref && !bit_x){
                if(trie[0][node])res = min(res, mn[trie[0][node]]);
                if(trie[1][node]){
                    node = trie[1][node];
                }
                else{
                    flag = 0;
                    break;
                }
            }
            else if(!bit_pref && bit_x){
                if(trie[1][node]){
                    node = trie[1][node];
                }
                else{
                    flag = 0;
                    break;
                }
            }
            else{
                if(trie[1][node])res = min(res, mn[trie[1][node]]);
                if(trie[0][node]){
                    node = trie[0][node];
                }
                else{
                    flag = 0;
                    break;
                }
            }
        }
        if(flag)res = min(res, mn[node]);
        return res;
    }
};
int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int n, x;
    cin >> n >> x;
    vector<int>v(n + 1), pref(n + 1);
    for(int i = 1;i <= n;++i){
        cin >> v[i];
        pref[i] = (pref[i - 1] ^ v[i]);
    }
    Trie trie(30 * n);
    trie.Update(pref[0], 0);
    int id = 0, mx = 0;
    for(int i = 1;i <= n;++i){
        int indx = trie.Get(pref[i], x);
        if(i - indx > mx){
            id = indx + 1;
            mx = i - indx;
        }
        else if(i - indx == mx && indx + 1 < id){
            id = indx + 1;
        }
        trie.Update(pref[i], i);
    }
    cout << id << " " << mx << '\n';
}

• Subtask 1: 100 / 100