제출 #1354514

#제출 시각아이디문제언어결과실행 시간메모리
1354514vjudge1XOR (IZhO12_xor)C++20
0 / 100
4 ms3368 KiB
#include <bits/stdc++.h>
using namespace std;

int ch[250005][2], mn[250005], sz = 0, x;

int newnode()
{
    ++sz;
    ch[sz][0] = ch[sz][1] = 0;
    mn[sz] = 1e9;
    return sz;
}

void add(int v, int id)
{
    int u = 0;
    mn[u] = min(mn[u], id);
    for (int bit = 29; bit >= 0; bit--)
    {
        int c = (v >> bit) & 1;
        if (!ch[u][c])
            ch[u][c] = newnode();

        u = ch[u][c];
        mn[u] = min(mn[u], id);
    }
}

int ask(int v)
{
    int u = 0, ans = 1e9;
    for (int bit = 29; bit >= 0; bit--)
    {
        int c = (v >> bit) & 1;
        int k = (x >> bit) & 1;
        if (k == 0)
        {
            int t = ch[u][c ^ 1];
            if (t)
                ans = min(ans, mn[t]);

            u = ch[u][c];
            if (!u)
                return ans;
        }
        else
        {
            u = ch[u][c ^ 1];
            if (!u)
                return ans;
        }
    }

    ans = min(ans, mn[u]);
    return ans;
}

int main()
{
	ios_base::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);
	
	int n;
    cin >> n >> x;

    mn[0] = 1e9;
    add(0, 0);

    int p = 0, bl = 0, bs = 0;
    for (int i = 1; i <= n; i++)
    {
        int a;
        cin >> a;
        p ^= a;

        int t = ask(p);
        if (t != 1e9)
        {
            int l = i - t;
            int s = t + 1;
            if (l > bl || (l == bl && (bs == 0 || s < bs)))
            {
                bl = l;
                bs = s;
            }
        }

        add(p, i);
    }

    cout << bs << ' ' << bl;
	
return 0;
}
#Verdict Execution timeMemoryGrader output
Fetching results...