Submission #49880

#	Time	Username	Problem	Language	Result	Execution time	Memory
49880		mra2322001	XOR (IZhO12_xor)	C++14	100 / 100	262 ms	72324 KiB

xor

//Solution by Ali-Amir Aldan
#include <algorithm>
#include <iostream>
#include <cstring>
#include <cassert>
#include <cstdio>
#include <vector>
#include <cmath>
#include <map>
#include <set>

using namespace std;

#define MAXN 250003
#define MAXVER 13000000

int n, x, last;
int a[MAXN];

int link[MAXVER][2];
int val[MAXVER];

int main ()
{

	scanf ("%d%d", &n, &x);
	for (int i = 0, y; i < n; i++)
	{
		scanf ("%d", &y);
		a[i+1] = a[i]^y;
	}

	int res = 0, pos = 0;
	memset (val, 127, sizeof (val));

	for (int i = 0, j, k, bit; i < n; i++)
	{
		for (j = 29, k = 0; j >= 0; j--)
		{
			val[k] = min (val[k], i);
			bit = (a[i]>>j)&1;
			if (!link[k][bit])
				link[k][bit] = ++last,
				assert (last < (MAXVER));
			k = link[k][bit];
		}
		val[k] = min (val[k], i);

		for (j = 29, k = 0; j >= 0; j--)
		{
			bit = (a[i+1]>>j)&1;

			if (link[k][bit^1] && !((x>>j)&1))
				if (i+1-val[link[k][bit^1]]>res)
					res = i+1-val[link[k][bit^1]],
					pos = val[link[k][bit^1]];

			bit ^= (x>>j)&1;

			if (!link[k][bit]) break;

			k = link[k][bit];
		}

		if (j < 0 && i+1-val[k]>res)
			res = i+1-val[k],
			pos = val[k];
	}

	printf ("%d %d\n", pos+1, res);

	return 0;
}

Compilation message (stderr)

xor.cpp: In function 'int main()':
xor.cpp:26:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf ("%d%d", &n, &x);
  ~~~~~~^~~~~~~~~~~~~~~~
xor.cpp:29:9: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf ("%d", &y);
   ~~~~~~^~~~~~~~~~

• Subtask 1: 100 / 100