Submission #1307809

#	Time	Username	Problem	Language	Result	Execution time	Memory
1307809		mosaab	XOR (IZhO12_xor)	C++17	100 / 100	171 ms	84656 KiB

xor

// عَجَبًا لأَمْرِ المُؤْمِنِ، إنَّ أمْرَهُ كُلَّهُ خَيْرٌ
#include <iostream>
using namespace std;
using ll = long long;
const char el = '\n';

struct Trie {
    Trie *p[2]{};
    int mn{1000000000}, lz{}, i{};

    void prp() {
        if (lz >> i & 1)
            swap(p[0], p[1]);
        if (p[0]) p[0]->lz ^= lz;
        if (p[1]) p[1]->lz ^= lz;
        lz = 0;
    }

    void insert(int x, int idx) {
        prp();
        mn = min(mn, idx);
        if (i == -1) return;
        if (x >> i & 1) {
            if (!p[1]) p[1] = new Trie(), p[1]->i = i - 1;
            p[1]->insert(x, idx);
        } else {
            if (!p[0]) p[0] = new Trie(), p[0]->i = i - 1;
            p[0]->insert(x, idx);
        }
    }

    int query(int l) {
        prp();
        if (i == -1) return mn;
        int ans = 1000000000;
        if (l >> i & 1)
            return p[1] ? p[1]->query(l) : ans;
        if (p[1]) ans = min(ans, p[1]->mn);
        if (p[0]) ans = min(ans, p[0]->query(l));
        return ans;
    }
};

void unsolve() {
    int n, x;
    cin >> n >> x;
    Trie s;
    s.i = 30;
    s.insert(0, 0);
    int len = 0, idx = 1;
    for (int i = 1, v, xr = 0; i <= n; i++) {
        cin >> v;
        xr ^= v;
        s.insert(xr, i);
        s.lz ^= xr;
        int q = s.query(x);
        s.lz ^= xr;
        if (i - q > len) {
            len = i - q;
            idx = q + 1;
        }
    }
    cout << idx << ' ' << len;
}

signed main() {
    cin.tie(0)->sync_with_stdio(0);
#if Mosaab
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
#endif
    int t = 1;
    // cin >> t;
    while (t--) unsolve();
}

• Subtask 1: 100 / 100