Submission #1149231

#	Time	Username	Problem	Language	Result	Execution time	Memory
1149231		hoksha	XOR (IZhO12_xor)	C++20	100 / 100	97 ms	42436 KiB

xor

#include "bits/stdc++.h"
using namespace std;
const int M = 31;
struct Node{
    int ch[2]{};
    int sz = 0;
    int mnIndex = 1e9;
    int isEnd = 0;
    int &operator[](char x){
        return ch[x];
    }
};
struct Trie{
    vector<Node>trie;

    int newNode(){
        trie.emplace_back();
        return trie.size() - 1;
    }
    Trie(){init();}
    void init() {
        trie.clear();
        trie.emplace_back();
    }
    void insert(int num, int index){
        int cur = 0;
        for(int i = M;  i>= 0; i--){
            int bit = num >>i & 1;
            if (trie[cur][bit] == 0) trie[cur][bit] = newNode();
            cur = trie[cur][bit];
            trie[cur].mnIndex = min(trie[cur].mnIndex,index);
        }
        trie[cur].isEnd++;
    }

    int getAns(int pre, int x){
        int cur = 0;
        int minAns = 1e9;
        for(int i = M; i >= 0; --i){
            int bitP = pre >> i & 1;
            int bitX = x >> i & 1;
            if (bitP == 1 && bitX == 0){
                if (trie[cur][0]){
                    minAns = min(minAns, trie[trie[cur][0]].mnIndex);
                }
            }
            else if (bitP == 0 && bitX == 0){
                if (trie[cur][1]){
                    minAns = min(minAns, trie[trie[cur][1]].mnIndex);
                }
            }


            if (trie[cur][bitP ^ bitX]){
                cur = trie[cur][bitP ^ bitX];
            }
            else break;
        }
        if(trie[cur].isEnd){
            minAns = min(minAns, trie[cur].mnIndex);
        }
        return minAns;
    }


};
void fast() {
    ios::sync_with_stdio(0);
    cin.tie(NULL);
    cout.tie(0);

}
int main(){
    fast();
    int n, x; cin >> n >> x;
    vector<int>a(n + 1);
    for(int i = 1; i <= n; ++i){
        cin >> a[i];
        a[i] ^= a[i - 1];
    }
    Trie trie;
    trie.insert(0, 0);
    int mxL = 0, L = 1e9;
    for(int i = 1; i <= n; i++){
        int minI  = trie.getAns(a[i], x);
        if (minI== 1e9){
            trie.insert(a[i], i);
            continue;
        }
        if (i  - minI > mxL){
            mxL = i - minI;
            L = minI + 1;
        }
        else if (i - minI == mxL){
            if (minI + 1< L){
                L = minI + 1;
            }
        }
        trie.insert(a[i], i);
    }
    cout << L << ' ' << mxL << endl;





    return 0;
}

• Subtask 1: 100 / 100