Submission #1141255

#TimeUsernameProblemLanguageResultExecution timeMemory
1141255samy_nagyXOR (IZhO12_xor)C++20
0 / 100
1 ms320 KiB
#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, a;
    int c{}, mx{};
    for (int i = 0; i < n; ++i) {
        int u;
        cin >> u;
        c ^= u;
        a.emplace_back(u);
        pref.emplace_back(c);
        mx = max(mx, u);
    }
    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{};
    if (mx >= x) {
        k = 1;
        for (int i = 0; i < n; ++i) {
            if (a[i] == mx) {
                st = i;
                break;
            }
        }
    }
    for (int i = 0; i < n; ++i) {
        int prefR = pref[i];
        tree.insert(prefR);
        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);
        }
    }
    if (st == 0) {
        st++;
        k--;
    }
    cout << st << " " << k;
    assert(k > 0);

}

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";

    }
}
#Verdict Execution timeMemoryGrader output
Fetching results...