Submission #876949

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
876949	2023-11-22T14:48:15 Z	boris_mihov	XOR (IZhO12_xor)	C++17	100 / 100	114 ms	91416 KB

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.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	16 ms	89180 KB	Output is correct
2	Correct	16 ms	89180 KB	Output is correct
3	Correct	17 ms	89120 KB	Output is correct
4	Correct	17 ms	89180 KB	Output is correct
5	Correct	23 ms	89392 KB	Output is correct
6	Correct	23 ms	89404 KB	Output is correct
7	Correct	25 ms	89436 KB	Output is correct
8	Correct	24 ms	89436 KB	Output is correct
9	Correct	47 ms	90260 KB	Output is correct
10	Correct	46 ms	90192 KB	Output is correct
11	Correct	46 ms	90196 KB	Output is correct
12	Correct	48 ms	90252 KB	Output is correct
13	Correct	48 ms	90256 KB	Output is correct
14	Correct	44 ms	90104 KB	Output is correct
15	Correct	43 ms	90200 KB	Output is correct
16	Correct	43 ms	90192 KB	Output is correct
17	Correct	95 ms	91228 KB	Output is correct
18	Correct	114 ms	91416 KB	Output is correct
19	Correct	105 ms	91412 KB	Output is correct
20	Correct	93 ms	91264 KB	Output is correct