Submission #896607

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
896607	2024-01-01T17:41:27 Z	borisAngelov	XOR (IZhO12_xor)	C++17	100 / 100	80 ms	96340 KB

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)
    {
        trie[node].minPos = min(trie[node].minPos, pos);

        if (bit == -1)
        {
            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);
    }

    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;

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

        if (trie[node].children[hasBit] != -1 && currentXor + (1 << bit) - 1 >= minXor)
        {
            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.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	18 ms	94800 KB	Output is correct
2	Correct	18 ms	94812 KB	Output is correct
3	Correct	17 ms	94952 KB	Output is correct
4	Correct	18 ms	94812 KB	Output is correct
5	Correct	21 ms	95124 KB	Output is correct
6	Correct	26 ms	95068 KB	Output is correct
7	Correct	24 ms	95064 KB	Output is correct
8	Correct	23 ms	95064 KB	Output is correct
9	Correct	38 ms	95404 KB	Output is correct
10	Correct	39 ms	95324 KB	Output is correct
11	Correct	38 ms	95324 KB	Output is correct
12	Correct	38 ms	95164 KB	Output is correct
13	Correct	37 ms	95312 KB	Output is correct
14	Correct	37 ms	95324 KB	Output is correct
15	Correct	38 ms	95320 KB	Output is correct
16	Correct	41 ms	95376 KB	Output is correct
17	Correct	75 ms	96084 KB	Output is correct
18	Correct	72 ms	96080 KB	Output is correct
19	Correct	80 ms	96340 KB	Output is correct
20	Correct	74 ms	96336 KB	Output is correct