Submission #330922

#	Time	Username	Problem	Language	Result	Execution time	Memory
330922		ZwariowanyMarcin	XOR (IZhO12_xor)	C++14	100 / 100	167 ms	23532 KiB

xor

#include <bits/stdc++.h>
#define pb push_back
#define fi first
#define se second
#define sz(x) (int)x.size()

using ll = long long;
using namespace std;

const int M = 8000000;

int n, q, a, b, cnt, to[M][2], mn[M];
pair<int, int> res;

void add(int pos, int x) {
	int v = 0;
	for (int i = 30; 0 <= i; --i) {
		int b = (x >> i & 1);
		if (!to[v][b]) to[v][b] = ++cnt, mn[cnt] = 1 << 30;
		v = to[v][b];
		mn[v] = min(mn[v], pos);
	}
}

int query(int x) {
	int v = 0, res = 1 << 30;
	for (int i = 30; 0 <= i; --i) {
		int b = (x >> i & 1);
		if (q >> i & 1) 
			v = to[v][!b];
		else {
			res = min(res, mn[to[v][!b]]);
			v = to[v][b];
		}
		if (!v) return res;
	}
	res = min(res, mn[v]);
	return res;
}			

int main() {
	//~ memset(mn, 0x3f, sizeof mn);
	mn[0] = 1 << 30;
	scanf("%d%d", &n, &q);
	add(0, 0);
	for (int i = 1; i <= n; ++i) {
		scanf("%d", &a);
		b ^= a;
		int l = query(b);
		res = max(res, {i - l, -l});
		add(i, b);
	}
	printf("%d %d\n", -res.second + 1, res.first);
	return 0;
}

Compilation message (stderr)

xor.cpp: In function 'int main()':
xor.cpp:44:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   44 |  scanf("%d%d", &n, &q);
      |  ~~~~~^~~~~~~~~~~~~~~~
xor.cpp:47:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   47 |   scanf("%d", &a);
      |   ~~~~~^~~~~~~~~~

• Subtask 1: 100 / 100