Submission #225289

#	Time	Username	Problem	Language	Result	Execution time	Memory
225289		cgiosy	XOR (IZhO12_xor)	C++17	0 / 100	5 ms	512 KiB

xor

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

struct iii { int l, r, k; };
int main() {
	ios::sync_with_stdio(0);cin.tie(0);
	int N, M, K=0, m=0, id=1;
	cin>>N>>M;
	vector<int> A(N+1);
	for(int i=1; i<=N; i++) cin>>A[i], A[i]^=A[i-1];

	vector<iii> T((N+1)*31, {0, 0, INT_MAX});
	for(int i=0; i<=N; i++) {
		int x=A[i];
		for(int p=1, d=31; d--;) {
			auto&[l,r,k]=T[p];
			if(x&1<<d) p=r=r?:++id;
			else p=l=l?:++id;
			T[p].k=min(T[p].k, i);
		}
	}
	for(int i=0; i<=N; i++) {
		int x=A[i], j=i;
		for(int p=1, d=31; d-- && p;) {
			auto[l,r,k]=T[p];
			if(x&1<<d) {
				if(M&1<<d) p=l;
				else j=min(j, T[l].k), x^=1<<d, p=r;
			} else if(M&1<<d) x^=1<<d, p=r;
			else j=min(j, T[r].k), p=l;
			if(x>=M) { j=min(j, T[p].k); break; }
		}
		if(m<i-j) m=i-j, K=j+1;
	}
	cout<<K<<' '<<m;
}

Compilation message (stderr)

xor.cpp: In function 'int main()':
xor.cpp:16:15: warning: unused variable 'k' [-Wunused-variable]
    auto&[l,r,k]=T[p];
               ^
xor.cpp:25:14: warning: unused variable 'k' [-Wunused-variable]
    auto[l,r,k]=T[p];
              ^

• Subtask 1: 0 / 100