Submission #453713

#	Time	Username	Problem	Language	Result	Execution time	Memory
453713		keta_tsimakuridze	XOR (IZhO12_xor)	C++14	100 / 100	218 ms	44356 KiB

xor

#include<bits/stdc++.h>
#define f first
#define s second
#define int long long
#define pii pair<int,int>
using namespace std;
const int N = 3e5 + 5, mod = 1e9 + 7; // !
int t,aft[32*N][2],mn[32*N],id,a,n;
void add(int x,int ind) {
	int u = 0;
	for(int i=32;i>=0;i--) {
		int b = ((1ll<<i)&x ? 1 : 0);
		if(!aft[u][b]) {
			id++;
			mn[id] = ind;
			aft[u][b] = id;
		}
		u = aft[u][b];
	}
}
int get(int x) {
	int ans = n + 1,u = 0;
	for(int i=32;i>=0;i--) {
		int b = ((1ll<<i)&x ? 1 : 0);
		if(!((1ll<<i) & a)) {
			ans = min(ans,mn[aft[u][1-b]]);
			if(!aft[u][b]) return ans;
			u = aft[u][b];
			continue;
		}
		if(!aft[u][1-b]) return ans;
		u = aft[u][1-b];
	}
	ans = min(ans,mn[u]);
	return ans;
}
main(){
	cin >> n >> a;
	mn[0] = n + 1;
	int ans = 0,p = 0,ind = 0;
	add(0,0);
	for(int i=1;i<=n;i++) {
		int b;
		cin >> b;
		p ^= b;
		int x = i - get(p);
		if(x > ans) {
			ans = x;
			ind = i - x + 1;
		}
		ans = max(ans,i - get(p));
		add(p,i);
	}
	cout<<ind<<" "<<ans;
 }

Compilation message (stderr)

xor.cpp:37:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   37 | main(){
      | ^~~~

• Subtask 1: 100 / 100