Submission #1141119

#	Time	Username	Problem	Language	Result	Execution time	Memory
1141119		b0udy	XOR (IZhO12_xor)	C++20	100 / 100	143 ms	57540 KiB

xor

#include <bits/stdc++.h>



#define Body  ios_base::sync_with_stdio(false);cin.tie(NULL);
#define fo(i , n) for (long long int i =0 ; i < n ; i++)
#define ll long long int

using namespace std;

const int N = 1e6+7, mod = 1e9+7 ;

int k ;

struct trie {
    trie *ls[2];
    int cnt;
    int front;
    trie() {
        memset(ls, 0, sizeof(ls));
        cnt = 0;
        front = N ;
    }
    void insert(ll x , int index) {
        trie *root = this;
        for (int j = 30; ~j; j--) {
            int bit = (x >> j) & 1;
            if (root->ls[bit] == nullptr) root->ls[bit] = new trie();
            root = root->ls[bit];
            root->cnt++;
            root->front = min(root->front , index);
        }
    }

    ll XOR(ll x) {
        trie *root = this;
        return calc(30 , x , 0 , root);
    }
    int calc(int j , int x , int cas , trie* root){
        if (root == nullptr)    return N ;
        if (cas || j == -1)    return root->front;
        int res = N ;
        int bit = (x >> j)&1 , bitk = (k >> j)&1 ;
        if (cas == 0){  // care
            if ((bit^bitk) == 0){
                if (bit)
                    res = calc(j-1 , x , 0 , root->ls[0]);
                else
                    res = min(calc(j-1 , x , 0 , root->ls[0]) , calc(j-1 , x , 1 , root->ls[1]));
            }else if (bit){
                res = min(calc(j-1 , x , 1 , root->ls[0]) , calc(j-1 , x , 0 , root->ls[bit]));
            }else{ // bitk == 1
                res = calc(j-1 , x , 0 , root->ls[1]);
            }
        }else{ // not care
            res = min(calc(j-1 , x , cas , root->ls[0]) , calc(j-1 , x , cas , root->ls[1]));
        }
        return res ;
    }
};

void burn() {
    int n ;
    cin >> n >> k ;
    int arr[n+1]{};
    fo(i , n){
        cin >> arr[i+1];
        arr[i+1] ^= arr[i];
    }
    trie trie;
    int idx = 0 , ln = 0 ;
    fo(i , n+1){
        trie.insert(arr[i] , i);
        if (i){
            int st = trie.XOR(arr[i]);
            if (i-st > ln) idx = st+1 , ln = i-st ;
            else if (i - st == ln) idx = min(st+1 , idx);
//            cout << trie.XOR(arr[i]) << ' ';
        }
    }
    cout << idx << ' ' << ln ;
}

int main() {
    Body
    int cas = 1 ;
//    cin >> cas ;
    while (cas--) {
        burn();
//        cout << endl;
    }
    return 0;
}

• Subtask 1: 100 / 100