Submission #896571

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
896571	2024-01-01T17:05:13 Z	borisAngelov	XOR (IZhO12_xor)	C++17	0 / 100	22 ms	94812 KB

xor

#include <bits/stdc++.h>

using namespace std;

const int maxn = 250005;
const int maxBits = 30;

int n, minXor;

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

int result = -1;

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

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

    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 = min(trie[trie[node].children[0]].minPos, trie[trie[node].children[1]].minPos);
    }

    void query(int node, int number, int pos, int bit, int currentXor)
    {
        if (bit == -1)
        {
            return;
        }

        if (currentXor >= minXor)
        {
            result = min(result, trie[node].minPos);
            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 ansLength = 0;
    int from = -1;
    int to = -1;

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

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

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

        if (result != n + 1)
        {
            ++result;

            if (ansLength < i - result + 1)
            {
                ansLength = i - result + 1;
                from = result;
                to = i;
            }
            else if (ansLength == i - result + 1 && from > result)
            {
                from = result;
                to = i;
            }
        }
    }

    cout << from << ' ' << ansLength << endl;

    return 0;
}

Compilation message

xor.cpp: In function 'int main()':
xor.cpp:105:9: warning: variable 'to' set but not used [-Wunused-but-set-variable]
  105 |     int to = -1;
      |         ^~

Subtask #1

0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Incorrect	22 ms	94812 KB	Output isn't correct
2	Halted	0 ms	0 KB	-