Submission #236656

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
236656	2020-06-02T17:44:19 Z	mohamedsobhi777	XOR (IZhO12_xor)	C++14	100 / 100	159 ms	54008 KB

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

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

Subtask #1

100.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	23 ms	37888 KB	Output is correct
2	Correct	22 ms	37888 KB	Output is correct
3	Correct	23 ms	37888 KB	Output is correct
4	Correct	24 ms	38016 KB	Output is correct
5	Correct	30 ms	38272 KB	Output is correct
6	Correct	31 ms	38272 KB	Output is correct
7	Correct	32 ms	38272 KB	Output is correct
8	Correct	33 ms	38392 KB	Output is correct
9	Correct	61 ms	44920 KB	Output is correct
10	Correct	62 ms	45464 KB	Output is correct
11	Correct	66 ms	45304 KB	Output is correct
12	Correct	67 ms	45304 KB	Output is correct
13	Correct	61 ms	45304 KB	Output is correct
14	Correct	62 ms	45304 KB	Output is correct
15	Correct	62 ms	45304 KB	Output is correct
16	Correct	62 ms	45304 KB	Output is correct
17	Correct	152 ms	53880 KB	Output is correct
18	Correct	148 ms	53880 KB	Output is correct
19	Correct	159 ms	53880 KB	Output is correct
20	Correct	156 ms	54008 KB	Output is correct