Official

C - ORXOR Editorial by en_translator


Try all the way to split \(A\) into one or more non-empty segments, and find one that yields the minimum value calculated in the way defined in the problem statement.
In order to try all the way to split \(A\) into one or more non-empty segments, we can try all the \(2^{N - 1}\) combinations of choosing the positions to put the “bars” out of \(N - 1\) positions between adjacent elements.
For implementation, a useful way is bitwise exhaustive search, in which each combination of \(N-1\) choices of whether or not to put the bars is regarded as \(N-1\)-digit binary integer, and corresponds to an integer between \(0\) (inclusive) and \(2^{N-1}\) (exclusive).

Sample Code (C++)

#include <bits/stdc++.h>

int ri() {
	int n;
	scanf("%d", &n);
	return n;
}

int main() {
	int n = ri();
	int a[n];
	for (auto &i : a) i = ri();
	
	int res = 2000000000;
	for (int i = 0; i < 1 << (n - 1); i++) {
		int xored = 0;
		int ored = 0;
		for (int j = 0; j <= n; j++) {
			if (j < n) ored |= a[j];
			if (j == n || (i >> j & 1)) xored ^= ored, ored = 0;
		}
		res = std::min(res, xored);
	}
	
	printf("%d\n", res);
	return 0;
}

posted:
last update: