Submission #1343689

#TimeUsernameProblemLanguageResultExecution timeMemory
1343689z1z0uXOR (IZhO12_xor)C++20
0 / 100
1 ms344 KiB
// بسم الله الرحمن الرحيم
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define el "\n"
#define sp " "

const int oo = 2e18, Mod = 1e9 + 7;
const int N = 1e5;
struct BinaryTrie
{
    struct node
    {
        node *ch[2];
        int cnt;
        int mnIdx;
        node()
        {
            ch[0] = ch[1] = 0;
            cnt = 0;
            mnIdx = 1e9;
        }
    };
    BinaryTrie()
    {
        // insert(0, 0);
    }
    node *root = new node();
    void insert(int n, int i)
    {
        node *curr = root;
        for (int bit = 30; bit >= 0; bit--)
        {
            bool idx = (1LL << bit) & n;
            if (curr->ch[idx] == 0)
            {
                curr->ch[idx] = new node();
            }
            curr = curr->ch[idx];
            curr->mnIdx = min(curr->mnIdx, i);
            curr->cnt++;
        }
    }
    int query(int n, int k)
    {
        int ans = 1e9;
        node *curr = root;
        for (int bit = 30; bit >= 0; bit--)
        {
            if (curr == 0)
                break;
            bool bn = (1LL << bit) & n;
            bool bk = (1LL << bit) & k;
            if (bk)
            {
                if (curr->ch[bn ^ 1] != 0)
                    ans = min(ans, curr->ch[bn ^ 1]->mnIdx);
                curr = curr->ch[bn ^ 1];
            }
            else
            {
                if (curr->ch[bn ^ 1] != 0)
                {
                    ans = min(ans, curr->ch[bn ^ 1]->mnIdx);
                    curr = curr->ch[bn ^ 1];
                }
                else
                {
                    curr = curr->ch[bn];
                }
            }
        }
        if (curr)
            ans = min(ans, curr->mnIdx);
        return ans;
    }
};

void Art()
{
    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];
    }
    BinaryTrie trie;
    int L = 1, K = 0;
    for (int i = 1; i <= n; i++)
    {
        int j = trie.query(v[i], x);
        if (j != 1e9)
        {
            if (i - j > K)
            {
                K = i - j;
                L = j + 1;
            }
        }
        trie.insert(v[i], i);
    }
    cout << L << sp << K << el;
}

signed main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(NULL);
    int tc = 1;
    // cin >> tc;
    while (tc--)
    {
        Art();
    }
    return 0;
}
#Verdict Execution timeMemoryGrader output
Fetching results...