Submission #1141249

#	Time	Username	Problem	Language	Result	Execution time	Memory
1141249		samy_nagy	XOR (IZhO12_xor)	C++20	0 / 100	0 ms	320 KiB

xor

#include <bits/stdc++.h>
/// لتكن مشيئتك
#define int long long
#define ll long long
using namespace std;
const int N = 1e3 + 5, mod = 1e9 + 7;// 1e9+7, 998244353
struct BinaryTrie {
    struct Node {
        Node *ch[2];
        int frq[2];

        Node() {
            memset(ch, 0, sizeof ch);
            memset(frq, 0, sizeof frq);
        }
    };

    Node *root = new Node();
    int mxBit;

    BinaryTrie(int bt) {
        mxBit = bt;
    }

    void insert(int n) {
        Node *curr = root;
        for (int i = mxBit; ~i; --i) {
            int idx = ((1ll << i) & n ? 1 : 0);
            if (curr->ch[idx] == 0) {
                curr->ch[idx] = new Node();
            }
            curr->frq[idx]++;
            curr = curr->ch[idx];
        }
    }


    int Query(int x) {
        Node *curr = root;
        int res{};
        for (int i = mxBit; ~i; --i) {
            int idx = ((1ll << i) & x ? 1 : 0);
            if (curr->ch[!idx] != 0) {
                curr = curr->ch[!idx];
                res |= (1ll << i) * (!idx);
            } else {
                curr = curr->ch[idx];
            }
        }
        return res;
    }

};

void solve() {
    int n, x;
    cin >> n >> x;
    vector<int> pref;
    int c{};
    for (int i = 0; i < n; ++i) {
        int u;
        cin >> u;
        c ^= u;
        pref.emplace_back(c);
    }
    if (pref.back() >= x) {
        cout << 1 << " " << n;
        return;
    }
    map<int, int> mp;
    for (int i = 0; i < n; ++i) {
        if (!mp.count(pref[i]))mp[pref[i]] = i + 1;
        // cout << pref[i] << " ";
    }
    // cout << endl;
    BinaryTrie tree(32);
    tree.insert(0);
    mp[0] = 0;

    int k{}, st{};
    for (int i = 0; i < n; ++i) {
        int prefR = pref[i];
        int R = i + 1;
        int prefL = tree.Query(prefR);
//        cout << prefR << " " << R << " " << prefL << endl;
        if (mp.count(prefL) and (prefL ^ prefR) >= x) {
            int L = mp[prefL];
            if (k < R - L + 1) {
                k = R - L + 1;
                st = L;
            } else if (k == R - L + 1)st = min(st, L);
        }
        tree.insert(prefR);
    }
    if (st == 0) {
        st++;
        k--;
    }
    cout << st << " " << k;

}

signed main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);


    int tc = 1;
    // cin >> tc;
    for (int i = 1; i <= tc; ++i) {
        solve();
        //  cout << "\n";

    }
}

• Subtask 1: 0 / 100