Submission #691018

#	Time	Username	Problem	Language	Result	Execution time	Memory
691018		danikoynov	XOR (IZhO12_xor)	C++14	100 / 100	197 ms	109856 KiB

xor

/**
 ____ ____ ____ ____ ____ ____
||l |||e |||i |||n |||a |||d ||
||__|||__|||__|||__|||__|||__||
|/__\|/__\|/__\|/__\|/__\|/__\|

**/

#include<bits/stdc++.h>
#define endl '\n'

using namespace std;
typedef long long ll;

void speed()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
}

const int maxn = 3e5 + 10;

struct trie
{
    int child[2], mx;

    trie()
    {
        child[0] = child[1] = -1;
        mx = 1e9;
    }
};

trie tree[30 * maxn];
int n, k, a[maxn], pref[maxn], last_used;
int max_len = 0, st_pos = 1;

void add(int root, int x, int depth, int idx)
{
    tree[root].mx = min(tree[root].mx, idx);
    if (depth < 0)
        return;

    int bit = (1 << depth), type = ((x & bit) > 0), &go = tree[root].child[type];
    if (go == -1)
        go = ++ last_used;

    add(go, x, depth - 1, idx);
}

void query(int root, int x, int depth, int idx)
{
    if (root == -1)
        return;

    if (depth < 0)
    {
        if (idx - tree[root].mx > max_len ||
            (idx - tree[root].mx == max_len &&
             tree[root].mx + 1 < st_pos))
        {
            max_len = idx - tree[root].mx;
            st_pos = tree[root].mx + 1;
        }
        return;
    }

    int bit = (1 << depth), type = ((x & bit) > 0), ktype = ((k & bit) > 0);
    if (ktype == 0)
    {
        int go = tree[root].child[(type + 1) % 2];
        if (go != -1)
        {
            if (idx - tree[go].mx > max_len ||
                (idx - tree[go].mx == max_len &&
                 tree[go].mx + 1 < st_pos))
            {
                max_len = idx - tree[go].mx;
                st_pos = tree[go].mx + 1;
            }
        }
        query(tree[root].child[type], x, depth - 1, idx);
    }
    else
    {
        query(tree[root].child[(type + 1) % 2], x, depth - 1, idx);
    }
}

void solve()
{
    cin >> n >> k;
    for (int i = 1; i <= n; i ++)
    {
        cin >> a[i];
        pref[i] = (pref[i - 1] ^ a[i]);
    }

    add(0, 0, 29, 0);
    for (int i = 1; i <= n; i ++)
    {
        query(0, pref[i], 29, i);
        add(0, pref[i], 29, i);
    }

    cout << st_pos << " " << max_len << endl;

}

int main()
{
    solve();
    return 0;
}

• Subtask 1: 100 / 100