Submission #429646

#	Time	Username	Problem	Language	Result	Execution time	Memory
429646		SuckTinHock	XOR (IZhO12_xor)	C++14	100 / 100	167 ms	25224 KiB

xor

#include <bits/stdc++.h>

using namespace std;
const int INF = INT_MAX;
int Trie[10000005][2];
int minn[10000005];
int n, x, S[250005];
int cnt = 0;
int D[250005];
int resi, resk = 0;

void add(int k, int id)
{
    int node = 0;
    for (int i = 30; i >= 0; --i)
    {
        int c = (k >> i) & 1;
        if (Trie[node][c] == 0)
        {
            Trie[node][c] = ++cnt;
            minn[Trie[node][c]] = id;
        }
        minn[Trie[node][c]] = min(minn[Trie[node][c]], id);
        node = Trie[node][c];
    }
}

int get(int k)
{
    int node = 0;
    int res = INF;
    for (int i = 30; i >= 0; --i)
    {
        int c = (k >> i) & 1;
        int bitx = (x >> i) & 1;
        if (bitx == 1)
        {
            if (Trie[node][1 - c] == 0) return res;
            node = Trie[node][1 - c];
        }
        else
        {
            if (Trie[node][1 - c] != 0) res = min(res, minn[Trie[node][1-c]]);
            if (Trie[node][c] == 0) return res;
            node = Trie[node][c];
        }
    }
    return min(res, minn[node]);
}

void xuly()
{
    add(0,0);
    for (int i = 1; i <= n; ++i)
    {
        D[i] = get(S[i]);
        add(S[i],i);
    }
    for (int i = 1; i <= n; ++i)
    {
        if (D[i] == INF) continue;
        if (resk < i - D[i])
        {
            resk = i - D[i];
            resi = D[i] + 1;
        }
        if (resk == i - D[i])
        {
            resi = min(resi, D[i] + 1);
        }
    }
    cout << resi << " " << resk;
}

void nhap()
{
    int t;
    cin >> n >> x;
    for (int i = 1; i <= n; ++i) cin >> t, S[i] = S[i-1] ^ t;
}

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    nhap();
    xuly();
    return 0;
}

• Subtask 1: 100 / 100