Submission #1289337

#	Time	Username	Problem	Language	Result	Execution time	Memory
1289337		nemkho	XOR (IZhO12_xor)	C++17	0 / 100	1 ms	1592 KiB

xor

#include <bits/stdc++.h>
#define ll long long
#define fi first
#define se second
#define pr pair <int, int>
using namespace std;
const int N = 250005;
int a[N], XOR[N], val, n, ans = 0, ans_pos = 1e9 + 5;
struct Trie
{
    int child[N*26][26], _min[N*26], cnt = 0;
    void make_trie()
    {
        for (int i = 1; i < N; i++)
            _min[i] = 1e9 + 5;
    }
    void add (int x, int idx)
    {
        int u = 0;
        for (int i = 29; i >= 0; i--)
        {
            bool k = (x & (1 << i));
            if (child[u][k] == 0)
                child[u][k] = ++cnt;
            _min[u] = min(_min[u], idx);
            u = child[u][k];
        }
        _min[u] = min(_min[u], idx);
    }
    int get (int x, int val)
    {
        int u = 0, res = 1e9 + 5;
        for (int i = 29; i >= 0; i--)
        {
            bool k_x = (x & (1 << i));
            bool k_val = (val & (1 << i));
            if (child[u][k_x^1])
            {
                if (k_val == 0)
                    res = min(res, _min[child[u][k_x^1]]);
                if (k_val == 1)
                    u = child[u][k_x^1];
                else if (!child[u][k_x])
                    return res;
                else
                    u = child[u][k_x];
            }
            else if (k_val == 1)
                return res;
            else if (child[u][k_x])
                u = child[u][k_x];
            else
                return res;
        }
        return min(res, _min[u]);
    }
} trie;
void inp()
{
    cin >> n >> val;
    for (int i = 1; i <= n; i++)
    {
        cin >> a[i];
        XOR[i] = a[i] ^ XOR[i-1];
    }
}
void solve()
{
    trie.make_trie();
    for (int i = 1; i <= n; i++)
        cout << XOR[i] << " ";
    cout << "\n";
    trie.add(0, 0);
    for (int i = 1; i <= n; i++)
    {
        int tmp = trie.get(XOR[i], val);
        //cout << tmp << "\n";
        if (tmp <= n)
        {
            if (ans <= i - tmp)
            {
                if (ans_pos > tmp + 1 && ans == i - tmp)
                    ans_pos = tmp + 1;
                else if (ans != i - tmp)
                    ans_pos = tmp + 1;
                ans = i - tmp;
               // cout << tmp << " " << i << "\n";
            }
        }
        trie.add(XOR[i], i);
    }
    cout << ans_pos << " " << ans << "\n";
}
int main()
{
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);

    inp();
    solve();
}

• Subtask 1: 0 / 100