Submission #1192379

#	Time	Username	Problem	Language	Result	Execution time	Memory
1192379		mk72	XOR (IZhO12_xor)	C++20	100 / 100	108 ms	56660 KiB

xor

#include <bits/stdc++.h>
using namespace std;
#define endl "\n"
#define ll long long
#define all(x) x.begin(), x.end()
#define siz(x) (int)(x.size())
void Mk72(){
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
}
class Trie{
private:
    struct Node{
        Node* nxt[2]{};
        int prefix;
        int idx;
        Node(){
            memset(nxt, 0, sizeof nxt);
            prefix = 0;
            idx = 1e7;
        }
    };
    Node* root = new Node();
public:
    void insert(const int& x, const int& i){
        Node* cur = root;
        for(int j = 30; j >= 0; --j){
            int idx = (x >> j) & 1;
            if(cur->nxt[idx] == nullptr)
                cur->nxt[idx] = new Node();
            cur = cur->nxt[idx];
            cur->idx = min(i, cur->idx);
        }
    }
    int answer(const int& x, const int& k){
        Node* cur = root;
        int mn = 1e7;
        for(int j = 30; j >= 0; --j){
            int idx = (k >> j) & 1;
            int i = (x >> j) & 1;
            if(!idx){
                if(cur->nxt[i ^ 1] != nullptr)
                    mn = min(mn, cur->nxt[i ^ 1]->idx);
            }
            if(cur->nxt[i ^ idx] == nullptr)
                return mn;
            cur = cur->nxt[i ^ idx];
        }
        return min(mn, cur->idx);
    }
};
void solve() {
    int n, k;
    cin >> n >> k;
    Trie tr;
    tr.insert(0, 0);
    int x = 0;
    ll ans = 0, idx;
    for(int i = 1; i <= n; ++i){
        int a;
        cin >> a;
        x ^= a;
        tr.insert(x, i);
        a = tr.answer(x, k);
        if(i - a > ans){
            ans = i - a;
            idx = a + 1;
        }
    }
    cout << idx << ' ' << ans << endl;
}
// Don't forget check it take test case
int main() {
    Mk72();
    int T = 1;
    //cin >> T;
    while (T--) {
        solve();
    }
}

• Subtask 1: 100 / 100