Submission #896606

#	Time	Username	Problem	Language	Result	Execution time	Memory
896606		borisAngelov	XOR (IZhO12_xor)	C++17	100 / 100	117 ms	98168 KiB

xor

#include <bits/stdc++.h>

using namespace std;

const int maxn = 250005;
const int maxBits = 29;
const int inf = 1e9;

int n, minXor;

int a[maxn];
int pref[maxn];

int result = inf;

struct Trie
{
    struct Node
    {
        int children[2];
        int minPos;

        Node()
        {
            children[0] = -1;
            children[1] = -1;
            minPos = inf;
        }
    };

    Node trie[maxn * 32];

    int root = 1;
    int nodeCnt = 1;

    void addNumber(int node, int number, int pos, int bit)
    {
        if (bit == -1)
        {
            trie[node].minPos = min(trie[node].minPos, pos);
            return;
        }

        bool hasBit = ((number & (1 << bit)) > 0);

        if (trie[node].children[hasBit] == -1)
        {
            trie[node].children[hasBit] = ++nodeCnt;
        }

        addNumber(trie[node].children[hasBit], number, pos, bit - 1);

        trie[node].minPos = inf;

        if (trie[node].children[0] != -1)
        {
            trie[node].minPos = min(trie[node].minPos, trie[trie[node].children[0]].minPos);
        }

        if (trie[node].children[1] != -1)
        {
            trie[node].minPos = min(trie[node].minPos, trie[trie[node].children[1]].minPos);
        }
    }

    void query(int node, int number, int pos, int bit, int currentXor)
    {
        if (bit == -1)
        {
            if (currentXor >= minXor)
            {
                //cout << "found " << trie[node].minPos << endl;
                result = min(result, trie[node].minPos);
            }

            return;
        }

        //cout << number << " " << pos << " " << bit << " :: " << currentXor << endl;

        if (currentXor + (1 << (bit + 1)) - 1 < minXor)
        {
            return;
        }

        bool hasBit = ((number & (1 << bit)) > 0);

        if (trie[node].children[hasBit] != -1)
        {
            query(trie[node].children[hasBit], number, pos, bit - 1, currentXor);
        }

        if (trie[node].children[1 - hasBit] != -1)
        {
            query(trie[node].children[1 - hasBit], number, pos, bit - 1, currentXor + (1 << bit));
        }
    }
};

Trie trie;

void fastIO()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
}

int main()
{
    fastIO();

    cin >> n >> minXor;

    for (int i = 1; i <= n; ++i)
    {
        cin >> a[i];
    }

    trie.addNumber(1, 0, 0, maxBits);

    int ans = 0;
    int from = 0;

    for (int i = 1; i <= n; ++i)
    {
        pref[i] = (pref[i - 1] ^ a[i]);

        result = inf;
        trie.query(1, pref[i], i, maxBits, 0);

        trie.addNumber(1, pref[i], i, maxBits);

        if (result != inf)
        {
            ++result;

            if (ans < i - result + 1)
            {
                ans = i - result + 1;
                from = result;
            }
        }
    }

    cout << from << ' ' << ans << endl;

    return 0;
}

/*
4 6
6 1 2 4
4 3
6 1 2 4
*/

• Subtask 1: 100 / 100