제출 #1161694

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1161694		asdasdqwer	XOR (IZhO12_xor)	C++20	100 / 100	490 ms	139720 KiB

xor

#include <bits/stdc++.h>
using namespace std;

#define pii array<int,2>

struct Node {
    pii cld = {-1, -1};
    vector<int> ind;
};

Node root;
vector<Node> trie = {root};

void insert(int val, int id) {
    int idx = 0;
    trie[0].ind.push_back(id);
    for (int i=30;i>=0;i--) {
        int b1 = 0;
        if (((1<<i)&val) != 0) b1 = 1;
        if (trie[idx].cld[b1] == -1) {
            Node n1;
            trie[idx].cld[b1] = (int)trie.size();
            trie.push_back(n1);
        }
        idx = trie[idx].cld[b1];
        trie[idx].ind.push_back(id);
    }
}

int find_min(int val, int k) {
    int idx = 0;
    int res = 1e9;
    for (int i=30;i>=0;i--) {
        if (((1<<i)&k) != 0) {
            int b1 = 1;
            if (((1<<i)&val) != 0) b1 = 0;
            if (trie[idx].cld[b1] == -1) return res;
            idx = trie[idx].cld[b1];
        }

        else {
            int b1 = 0;
            if (((1<<i)&val) != 0) b1 = 1;
            if (trie[idx].cld[1-b1] != -1 && trie[trie[idx].cld[1-b1]].ind.size()) res = min(res, trie[trie[idx].cld[1-b1]].ind[0]);
            if (trie[idx].cld[b1] == -1) return res;
            idx = trie[idx].cld[b1];
        }
    }

    if (trie[idx].ind.size()) res = min(res, trie[idx].ind[0]);
    return res;
}

signed main() {
    int n,k;cin>>n>>k;
    vector<int> a(n);
    for (auto &x:a)cin>>x;
    vector<int> p(n, 0);
    p[0] = a[0];
    for (int i=1;i<n;i++) {
        p[i] = (p[i-1] ^ a[i]);
    }

    insert(0, -1);
    int mxDis = -1, mnI = -1;
    for (int i=0;i<n;i++) {
        int mn = find_min(p[i], k);
        if (i - mn > mxDis) {
            mxDis = i-mn;
            mnI = mn;
        }

        else if (i - mn == mxDis) {
            mnI = min(mnI, mn);
        }
        insert(p[i], i);
    }

    cout << mnI+2 << " " << mxDis << endl;
}

• Subtask 1: 100 / 100