Submission #508558

#	Time	Username	Problem	Language	Result	Execution time	Memory
508558		sidon	XOR (IZhO12_xor)	C++17	100 / 100	281 ms	44444 KiB

xor

#include <bits/stdc++.h>
using namespace std;

int N, X, pref, ind, k, curr, u;
int C[2][1<<22], t[1<<22];

void minim(int l, int r) {
	if(l && r-l > k) k = r-l, ind = l;
}

void go(bool c) {
	u = C[c][u] ? : C[c][u] = ++curr;
}

int main() {
	ios::sync_with_stdio(0), cin.tie(0);

	cin >> N >> X;

	for(int i = 1; i <= N + 1; i++) {
		u = 0;
		for(int j = 30; --j >= 0; ) {
			if(X & (1<<j)) {
				go(!(pref & (1<<j)));
				if(!j) minim(t[u], i);
			} else {
				minim(t[C[!(pref & (1<<j))][u]], i);
				go(pref & (1<<j));
			}
		}
		minim(t[u], i);
		u = 0;
		for(int j = 30; --j >= 0; ) {
			go(pref & (1<<j));
			t[u] = t[u] ? : i;
		}

		cin >> u;
		pref ^= u;
	}
	if(!X) ind = 1, k = N;

	cout << ind << ' ' << k;
}

• Subtask 1: 100 / 100