Submission #330920

#	Time	Username	Problem	Language	Result	Execution time	Memory
330920		ZwariowanyMarcin	XOR (IZhO12_xor)	C++14	0 / 100	2105 ms	197356 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 = 1 << 24;

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

int 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;
		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);
	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 add(int, int)':
xor.cpp:23:1: warning: no return statement in function returning non-void [-Wreturn-type]
   23 | }
      | ^
xor.cpp: In function 'int main()':
xor.cpp:43:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   43 |  scanf("%d%d", &n, &q);
      |  ~~~~~^~~~~~~~~~~~~~~~
xor.cpp:46:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   46 |   scanf("%d", &a);
      |   ~~~~~^~~~~~~~~~

• Subtask 1: 0 / 100