제출 #1359208

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1359208		Braabebo10	XOR (IZhO12_xor)	C++20	100 / 100	116 ms	85620 KiB

xor

#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int N = 1e6 + 5, mod = 1e9 + 7;
int dx[] = {0, 0, -1, 1, -1, -1, 1, 1};
int dy[] = {1, -1, 0, 0, -1, 1, -1, 1};
int n, k;

class Binary_Trie {
    struct Node {
        Node *bit[2];
        int freq[2], idx;

        Node() {
            memset(bit, 0, sizeof bit);
            memset(freq, 0, sizeof freq);
            idx = -1;
        }
    };

public:
    Node *root = new Node();

    Binary_Trie() {
        // insert(0, 1);
    }

    void insert(int x, int j) {
        Node *cur = root;
        for (int i = 30; ~i; i--) {
            int on = (((1 << i) & x) > 0);
            if (cur->bit[on] == 0) {
                cur->bit[on] = new Node();
            }
            cur = cur->bit[on];
            if (cur->idx == -1)
                cur->idx = j;
            cur->freq[on]++;
        }
    }

    int query(int x, int j) {
        int ret = 1e9;
        Node *cur = root;
        for (int i = 30; ~i; i--) {
            int on = (((1 << i) & x) > 0);
            int onk = (((1 << i) & k) > 0);
            if (onk) {
                if (cur->bit[on ^ 1] == 0)
                    return ret;
                cur = cur->bit[on ^ 1];
            } else {
                if (cur->bit[on ^ 1] != 0)
                    ret = min(ret, cur->idx);
                if (cur->bit[on] == 0)
                    return ret;
                cur = cur->bit[on];
            }
        }
        return min(ret, cur->idx);
    }
};

void solve() {
    cin >> n >> k;
    int a[n + 1];
    Binary_Trie tr;
    int mx = 0, st = 0;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
        if (a[i] >= k && mx == 0)
            st = i - 1, mx = 1;
        if (i > 1)
            a[i] ^= a[i - 1];
        int ans = tr.query(a[i], i);
        if (a[i] >= k)
            st = 0, mx = i;
        else if (ans != 1e9 && (!mx || (i - ans) > mx))
            mx = i - ans, st = ans;
        tr.insert(a[i], i);
    }
    cout << st + 1 << " " << mx;
}

int32_t main() {
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    int t = 1;
    // cin >> t;
    while (t--) {
        solve();
    }
    return 0;
}

• 서브태스크 1: 100 / 100