Submission #876949

#	Time	Username	Problem	Language	Result	Execution time	Memory
876949		boris_mihov	XOR (IZhO12_xor)	C++17	100 / 100	114 ms	91416 KiB

xor

#include <algorithm>
#include <iostream>
#include <numeric>
#include <cassert>
#include <vector>

typedef long long llong;
const int MAXN = 250000 + 10;
const int MAXLOG = 30;

int n, min;
struct Trie
{
    struct Node
    {
        int children[2];
        int min;

        Node()
        {
            min = 1e9;
            children[0] = children[1] = 0;
        }
    };

    int cnt;
    Node trie[MAXN * MAXLOG];

    void insert(int node, int bit, int value, int idx)
    {
        if (bit == -1)
        {
            trie[node].min = std::min(trie[node].min, idx);
            return;
        }

        int curr = (value & (1 << bit)) > 0;
        if (trie[node].children[curr] == 0)
        {
            trie[node].children[curr] = ++cnt;
        }

        insert(trie[node].children[curr], bit - 1, value, idx);
        trie[node].min = std::min(trie[trie[node].children[0]].min, trie[trie[node].children[1]].min);
    }

    int search(int node, int bit, int value, int allowed)
    {
        if (node == 0 || bit == -1)
        {
            return trie[node].min;
        }

        int curr = (value & (1 << bit)) == 0;
        int op   = curr ^ 1;

        if (trie[trie[node].children[op]].min < trie[trie[node].children[curr]].min && allowed < (1 << bit))
        {
            return search(trie[node].children[op], bit - 1, value, allowed);
        } else
        {
            return search(trie[node].children[curr], bit - 1, value, allowed - (1 << bit));
        }
    }

    void build()
    {
        cnt = 1;
    }

    void insert(int idx, int value)
    {
        insert(1, MAXLOG - 1, value, idx);
    }

    int search(int value)
    {
        return search(1, MAXLOG - 1, value, min);
    }
};

Trie trie;
int a[MAXN];

void solve()
{
    trie.build();
    trie.insert(0, 0);
    int value = 0;
    int ans = 0;
    int idx = 0;

    for (int i = 1 ; i <= n ; ++i)
    {
        value ^= a[i];
        int res = i - trie.search(value);
        if (res > ans)
        {
            ans = res;
            idx = i;
        }

        trie.insert(i, value);
    }

    std::cout << idx - ans + 1 << ' ' << ans << '\n';
}

void input()
{
    std::cin >> n >> min;
    for (int i = 1 ; i <= n ; ++i)
    {
        std::cin >> a[i];
    }
}

void fastIOI()
{
    std::ios_base :: sync_with_stdio(0);
    std::cout.tie(nullptr);
    std::cin.tie(nullptr);
}

int main()
{
    fastIOI();
    input();
    solve();

    return 0;
}

• Subtask 1: 100 / 100