Submission #1044738

#	Time	Username	Problem	Language	Result	Execution time	Memory
1044738		KN200711	XOR (IZhO12_xor)	C++14	0 / 100	0 ms	348 KiB

xor

# include <bits/stdc++.h>
# define ll long long
# define ld long double
# define pii pair<int, int>
# define fi first
# define se second
using namespace std;

int main() {
	int N;
	ll x;
	scanf("%d %lld", &N, &x);
	vector<ll> arr(N);
	for(int i=0;i<N;i++) {
		scanf("%lld", &arr[i]);
		if(i > 0) arr[i] ^= arr[i - 1];
	}
	
	int c = 1, len = 0;
	for(int i=0;i<=29;i++) {
		ll cek = (((1ll << i) - 1ll) << (30 - i));
		ll cc = (1ll << (29 - i));
		if(x&cc) continue;
		
		ll need = (x&cek) * 2ll + 1ll;
		map<ll, int> M;
		M.clear();
		
		M[0] = 0;
		for(int k=0;k<N;k++) {
			ll v = arr[k]&cek;
			ll v1 = arr[k]&cc;
			
			v = 2ll * v;
			if(v1) v++;
			
		//	cout<<"i : "<<i<<" "<<k<<" "<<v<<" "<<need<<endl;
			if(M.count(v ^ need)) {
				int nw = M[v ^ need];
			//	cout<<"k : "<<k<<" "<<nw<<endl;
				if(k + 1 - nw > len) {
					len = k + 1 - nw;
					c = nw + 1;
				} else if(k + 1 - nw == len) {
					c = min(c, nw + 1);
				}
			}
			if(!M.count(v)) M[v] = k + 1;
		}
	}
//	cout<<c<<" "<<len<<endl;
	map<ll, int> M;
	M.clear();
	
	M[0] = 0;
	for(int k=0;k<N;k++) {
		if(M.count(arr[k] ^ x)) {
			int v = M[arr[k] ^ x];
		//	cout<<arr[k]<<" "<<(arr[k] ^ x)<<" "<<k + 1 - v<<" "<<v + 1<<endl;
			if(k + 1 - v > len) {
				len = k + 1 - v;
				c = v + 1;
			} else if(k + 1 - v == len) {
				c = min(c, v + 1);
			}
			if(!M.count(arr[k])) M[arr[k]] = k + 1;
		}
	}
	if(len == 0) {
		printf("-1 -1\n");
		return 0;
	}
	
	printf("%d %d\n", c, len);
}

Compilation message (stderr)

xor.cpp: In function 'int main()':
xor.cpp:12:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   12 |  scanf("%d %lld", &N, &x);
      |  ~~~~~^~~~~~~~~~~~~~~~~~~
xor.cpp:15:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   15 |   scanf("%lld", &arr[i]);
      |   ~~~~~^~~~~~~~~~~~~~~~~

• Subtask 1: 0 / 100