Submission #650969

#	Time	Username	Problem	Language	Result	Execution time	Memory
650969		Elias_Obeid	XOR (IZhO12_xor)	C++17	100 / 100	207 ms	27960 KiB

xor

#include <bits/stdc++.h>
using namespace std;

const int INF = 1'000'000'000;

template <typename number_type, int alphabet_size>
class BinaryTrie
{
private:
    struct TrieNode
    {
        const static int BITS = 2;

        int best;
        array<int, BITS> next_nodes;
        TrieNode()
        {
            best = INF;
            next_nodes.fill(-1);
        }
    };

    int root;
    vector<TrieNode> nodes;
    int fetchNode()
    {
        nodes.emplace_back(TrieNode());
        return (int)nodes.size() - 1;
    }

public:
    BinaryTrie()
    {
        root = fetchNode();
    }

    void insert(number_type value, int id)
    {
        int current_node = root;
        for (int bit = alphabet_size; bit >= 0; --bit)
        {
            int value_bit = (value >> bit & 1);
            if (nodes[current_node].next_nodes[value_bit] == -1)
            {
                nodes[current_node].next_nodes[value_bit] = fetchNode();
            }
            current_node = nodes[current_node].next_nodes[value_bit];
            nodes[current_node].best = min(nodes[current_node].best, id);
        }
    }

    pair<int, int> getAnswer(int value, int K, int i)
    {
        int current_node = root;
        pair<int, int> answer{-1, -1};
        for (int bit = alphabet_size; bit >= 0; --bit)
        {
            if (current_node == -1)
            {
                return answer;
            }

            int k_bit = (K >> bit & 1);
            int value_bit = (value >> bit & 1);
            if (k_bit == 0)
            {
                if (nodes[current_node].next_nodes[value_bit ^ 1] != -1)
                {
                    int id = nodes[nodes[current_node].next_nodes[value_bit ^ 1]].best;
                    if (i - id > answer.second ||
                        (i - id == answer.second && id < answer.first))
                    {
                        answer = make_pair(id, i - id);
                    }
                }
                current_node = nodes[current_node].next_nodes[value_bit];
            }
            else
            {
                current_node = nodes[current_node].next_nodes[value_bit ^ 1];
            }
        }

        if (current_node != -1)
        {
            int id = nodes[current_node].best;
            if (i - id > answer.second ||
                (i - id == answer.second && id < answer.first))
            {
                answer = make_pair(id, i - id);
            }
        }
        return answer;
    }
};

int main()
{
    int N, K;
    cin >> N >> K;

    vector<int> prefix_xor(N + 1);
    for (int i = 1; i <= N; ++i)
    {
        int A;
        cin >> A;
        prefix_xor[i] = (prefix_xor[i - 1] ^ A);
    }

    BinaryTrie<int, 30> trie;
    trie.insert(0, 0);

    pair<int, int> answer{-1, -1};
    for (int i = 1; i <= N; ++i)
    {
        pair<int, int> current_answer = trie.getAnswer(prefix_xor[i], K, i);
        if (current_answer.second > answer.second ||
            (current_answer.second == answer.second && current_answer.first < answer.first))
        {
            answer = current_answer;
        }
        trie.insert(prefix_xor[i], i);
    }
    cout << answer.first + 1 << " " << answer.second << "\n";
    return 0;
}

• Subtask 1: 100 / 100