Submission #1166593

#	Time	Username	Problem	Language	Result	Execution time	Memory
1166593		ezzatw122	XOR (IZhO12_xor)	C++20	0 / 100	75 ms	35336 KiB

xor

#include <bits/stdc++.h>


// you just try again
using namespace std;
#define ll long long

void read() {
    ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
}

const int N = 2e5 + 5;

struct trie {
    struct node {
        int nxt[2];
        vector<int> idx;

        node() {
            nxt[0] = nxt[1] = -1;
        }
    };

    vector<node> tr;
    int sz;

    trie() {
        tr.push_back(node());
        sz = 0;
    }

    void update(int x, int idx) {
        int cur = 0;
        for (int i = 30; i >= 0; i--) {
            int bit = (x >> i) & 1;
            if (!~tr[cur].nxt[bit]) {
                tr.push_back(node());
                tr[cur].nxt[bit] = ++sz;
            }
            cur = tr[cur].nxt[bit];
        }
        tr[cur].idx.push_back(idx);
    }

    int query(int x, int k, int idx, bool ok = 0, int curr = 0) {
        int bitx = (x >> idx) & 1;
        int bitk = (k >> idx) & 1;
        int ret = 3e5;
        if (ok) {
            for (auto j: tr[curr].idx) {
                ret = min(ret, j);
            }
        }
        if (idx == -1) return ret;
        if (~tr[curr].nxt[0] && ((bitk && bitx) or ok))ret = min(ret, query(x, k, idx - 1, 0, tr[curr].nxt[0]));
        if (~tr[curr].nxt[0] && ((!bitk && !bitx) or ok))ret = min(ret, query(x, k, idx - 1, 0, tr[curr].nxt[0]));
        if (~tr[curr].nxt[0] && ((!bitk && bitx) or ok))ret = min(ret, query(x, k, idx - 1, 1, tr[curr].nxt[0]));


        if (~tr[curr].nxt[1] && ((bitk && !bitx) or ok))ret = min(ret, query(x, k, idx - 1, 0, tr[curr].nxt[1]));
        if (~tr[curr].nxt[1] && ((!bitk && !bitx) or ok))ret = min(ret, query(x, k, idx - 1, 1, tr[curr].nxt[1]));

        return ret;
    }
};

void code() {
    int n, x;
    cin >> n >> x;
    vector<int> v(n + 1);
    for (int i = 1; i <= n; i++) {
        cin >> v[i];
        v[i] = v[i - 1] ^ v[i];
    }
    trie tr;
    tr.update(0, 0);
    int mx = 0, idx = -1;
    for (int i = 1; i <= n; i++) {
        int len = i - tr.query(v[i], x - 1, 30);
        if (len > mx) {
            mx = len;
            idx = i;
        }
        tr.update(v[i], i);
    }
    cout << idx - mx + 1 << " " << mx << "\n";
}

int main() {
    read();
    int t = 1;
    // cin >> t;
    while (t--)
        code();
}

• Subtask 1: 0 / 100