Submission #896590

#	Time	Username	Problem	Language	Result	Execution time	Memory
896590		borisAngelov	XOR (IZhO12_xor)	C++17	0 / 100	31 ms	94940 KiB

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 = n + 1;

        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)
        {
            return;
        }

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

        if (currentXor >= minXor)
        {
            //cout << "found " << trie[node].minPos << endl;
            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];
    }

    /*int ans = 0;

    for (int i = 1; i <= n; ++i)
    {
        int curr = 0;

        for (int j = i; j <= n; ++j)
        {
            curr = (curr ^ a[j]);

            if (curr >= minXor)
            {
                ans = max(ans, j - i + 1);
            }
        }
    }*/

    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;
}

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

Compilation message (stderr)

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

• Subtask 1: 0 / 100