Submission #1359201

#TimeUsernameProblemLanguageResultExecution timeMemory
1359201Braabebo10XOR (IZhO12_xor)C++20
100 / 100
98 ms56536 KiB
#include <bits/stdc++.h>
#define ll long long
using namespace std;

const int N = 1e6 + 5;
const int INF = 1e9 + 7;

int n, k;

class Binary_Trie
{
    struct Node
    {
        Node *bit[2];
        int mn; // minimum prefix index in this subtree

        Node()
        {
            bit[0] = bit[1] = nullptr;
            mn = INF;
        }
    };

public:
    Node *root = new Node();

    Binary_Trie()
    {
        // insert prefix xor 0 at index 0
        insert(0, 0);
    }

    void insert(int x, int j)
    {
        Node *cur = root;
        cur->mn = min(cur->mn, j);

        for (int i = 30; i >= 0; i--)
        {
            int on = (x >> i) & 1;
            if (cur->bit[on] == nullptr)
                cur->bit[on] = new Node();

            cur = cur->bit[on];
            cur->mn = min(cur->mn, j);
        }
    }

    // returns the minimum prefix index j such that (x xor pref[j]) >= k
    int query(int x)
    {
        Node *cur = root;
        int ret = INF;

        for (int i = 30; i >= 0; i--)
        {
            int on = (x >> i) & 1;
            int kb = (k >> i) & 1;

            if (kb)
            {
                // must take xor bit = 1 here
                cur = cur->bit[on ^ 1];
                if (cur == nullptr)
                    return ret;
            }
            else
            {
                // if we take xor bit = 1 here, the number becomes already > k
                if (cur->bit[on ^ 1] != nullptr)
                    ret = min(ret, cur->bit[on ^ 1]->mn);

                // continue with xor bit = 0
                cur = cur->bit[on];
                if (cur == nullptr)
                    return ret;
            }
        }

        // exact match path also works
        ret = min(ret, cur->mn);
        return ret;
    }
};

void solve()
{
    cin >> n >> k;

    Binary_Trie tr;
    int pref = 0;

    int bestLen = 0;
    int bestStart = 1;

    for (int i = 1; i <= n; i++)
    {
        int a;
        cin >> a;
        pref ^= a;

        int j = tr.query(pref);
        if (j != INF)
        {
            int len = i - j;
            int start = j + 1;

            if (len > bestLen || (len == bestLen && start < bestStart))
            {
                bestLen = len;
                bestStart = start;
            }
        }

        tr.insert(pref, i);
    }

    cout << bestStart << " " << bestLen;
}

int32_t main()
{
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);

    int t = 1;
    while (t--)
    {
        solve();
        cout << '\n';
    }

    return 0;
}
#Result Execution timeMemoryGrader output
Fetching results...