Submission #236656

#	Time	Username	Problem	Language	Result	Execution time	Memory
236656		mohamedsobhi777	XOR (IZhO12_xor)	C++14	100 / 100	159 ms	54008 KiB

xor

#include <bits/stdc++.h>

using namespace std;

const int N = 3e5 + 7;

int n, k;
int trie[N*32][2];
int T = 1;
int vals[N * 32 ];

void mkm(int &x, int &v)
{
        if (vals[x] == -1)
        {
                vals[x] = v;
        }
        else
        {
                vals[x] = min(vals[x], v);
        }
}

void add(int ix, int x)
{
        int cur = 0;
        for (int i = 29; i >= 0; i--)
        {
                bool is = !!(x & (1 << i));
                if (!trie[cur][is])
                {
                        trie[cur][is] = T++;
                }
                cur = trie[cur][is];
                mkm(cur, ix);
        }
}

int query(int x)
{
        int ret = N;
        int cur = 0;
        int got = 0 ;
        for (int i = 29; i >= 0; i--)
        {
                int is = !!(k & (1 << i));
                int mb = !!(x & (1 << i));

                if (is)
                {
                        if (!trie[cur][!mb])
                        {
                                return N;
                        }
                        cur = trie[cur][!mb];
                }
                else
                {
                        if (trie[cur][!mb])
                        {
                                ret = min(ret, vals[trie[cur][!mb]]);
                        }

                        if(trie[cur][mb]){
                                cur = trie[cur][mb] ; 
                        }
                        else if(trie[cur][!mb]){
                                return min(ret , trie[cur][!mb]) ; 
                        }
                        else return N ; 
                }
        }
        ret = min(ret, vals[cur]);
        return ret;
}

int main()
{
        memset(vals, -1, sizeof vals);
        ios_base::sync_with_stdio(0);
        cin.tie(0);
        //freopen("in.in", "r", stdin);
        cin >> n >> k;
        int xr = 0;
        int ix = N;
        int ans = 0;
        add(0, 0);
        for (int i = 1; i <= n; i++)
        {
                int t;
                cin >> t;
                xr ^= t;
                add(i, xr);
                int sol = query(xr);
                if (i - sol > ans )
                {
                        ix = sol +1 ;
                        ans = i - sol ;
                }
        }
        cout << ix << " " << ans;
        return 0;
}

Compilation message (stderr)

xor.cpp: In function 'int query(int)':
xor.cpp:43:13: warning: unused variable 'got' [-Wunused-variable]
         int got = 0 ;
             ^~~

• Subtask 1: 100 / 100