답안 #963393

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
963393	2024-04-14T23:21:10 Z	biank	XOR (IZhO12_xor)	C++14	100 / 100	1644 ms	36880 KB

xor

#include <bits/stdc++.h>

using namespace std;

#define sz(x) int(x.size())

struct Trie {
    struct Node {
        int child[2];
        Node() {
            child[0] = child[1] = 0;
        }
    };
    vector<Node> trie;
    Trie() {
        trie.clear();
        trie.push_back(Node());
    }
    void insert(int x) {
        int u = 0;
        for (int i = 29; i >= 0; i--) {
            int b = x >> i & 1;
            if (!trie[u].child[b]) {
                trie[u].child[b] = sz(trie);
                trie.push_back(Node());
            }
            u = trie[u].child[b];
        }
    }
    int search(int x) {
        int u = 0;
        int ans = 0;
        for (int i = 29; i >= 0; i--) {
            int b = x >> i & 1;
            if (trie[u].child[b ^ 1]) {
                ans += 1 << i;
                u = trie[u].child[b ^ 1];
            } else if (trie[u].child[b]) {
                u = trie[u].child[b];
            } else {
                return 0;
            }
        }
        return ans;
    }
};

int check(vector<int> &a, int x, int k) {
    Trie trie;
    int n = sz(a);
    vector<int> pref(n + 1);
    pref[0] = 0;
    for (int i = 0; i < sz(a); i++) {
        pref[i + 1] = pref[i] ^ a[i];
        if (i >= k) {
            trie.insert(pref[i - k]);
            if (trie.search(pref[i + 1]) >= x) return i - k + 1;
        }
    }
    return 0;
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    
    int n, x;
    cin >> n >> x;
    vector<int> a(n);
    for (int i = 0; i < n; i++) {
        cin >> a[i];
    }
    
    int l = -1, r = n + 1;
    int ans = -1;
    while (l + 1 < r) {
        int m = (l + r) / 2;
        int i = check(a, x, m);
        if (i != 0) {
            l = m;
            ans = i;
        } else {
            r = m;
        }
    }
    cout << ans << ' ' << r << '\n';
    
    return 0;
}

Subtask #1

100.0 / 100.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	348 KB	Output is correct
2	Correct	1 ms	348 KB	Output is correct
3	Correct	1 ms	348 KB	Output is correct
4	Correct	3 ms	348 KB	Output is correct
5	Correct	59 ms	1484 KB	Output is correct
6	Correct	72 ms	1716 KB	Output is correct
7	Correct	81 ms	1756 KB	Output is correct
8	Correct	92 ms	1808 KB	Output is correct
9	Correct	559 ms	18288 KB	Output is correct
10	Correct	560 ms	18412 KB	Output is correct
11	Correct	529 ms	17488 KB	Output is correct
12	Correct	549 ms	16816 KB	Output is correct
13	Correct	532 ms	16968 KB	Output is correct
14	Correct	600 ms	17660 KB	Output is correct
15	Correct	528 ms	16852 KB	Output is correct
16	Correct	507 ms	17972 KB	Output is correct
17	Correct	1597 ms	35824 KB	Output is correct
18	Correct	1609 ms	36880 KB	Output is correct
19	Correct	1644 ms	36656 KB	Output is correct
20	Correct	1494 ms	35776 KB	Output is correct