답안 #49880

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
49880	2018-06-04T03:50:04 Z	mra2322001	XOR (IZhO12_xor)	C++14	100 / 100	262 ms	72324 KB

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

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.0 / 100.0

#	결과	실행 시간	메모리	Grader output
1	Correct	39 ms	51320 KB	Output is correct
2	Correct	39 ms	51356 KB	Output is correct
3	Correct	39 ms	51356 KB	Output is correct
4	Correct	39 ms	51372 KB	Output is correct
5	Correct	45 ms	51812 KB	Output is correct
6	Correct	47 ms	51864 KB	Output is correct
7	Correct	63 ms	51888 KB	Output is correct
8	Correct	57 ms	51996 KB	Output is correct
9	Correct	99 ms	58516 KB	Output is correct
10	Correct	96 ms	58516 KB	Output is correct
11	Correct	134 ms	58516 KB	Output is correct
12	Correct	101 ms	58564 KB	Output is correct
13	Correct	97 ms	58564 KB	Output is correct
14	Correct	103 ms	58564 KB	Output is correct
15	Correct	97 ms	58604 KB	Output is correct
16	Correct	109 ms	58604 KB	Output is correct
17	Correct	237 ms	66412 KB	Output is correct
18	Correct	221 ms	68460 KB	Output is correct
19	Correct	244 ms	70448 KB	Output is correct
20	Correct	262 ms	72324 KB	Output is correct