Submission #963326

#	Time	Username	Problem	Language	Result	Execution time	Memory
963326		Acanikolic	XOR (IZhO12_xor)	C++14	100 / 100	108 ms	79112 KiB

xor

#include <bits/stdc++.h>
		 		
//#define int long long 
		 
#define pb push_back 
		
#define F first
		 
#define S second
		 
using namespace std;
		 
const int N = 250010;
		 
const int mod = 1e9 + 7;
		 
const int inf = 1e9;

int pref[N],a[N],trie[N * 31][2],mn[N * 31 * 2],idx = 0;

void Add(int x,int i) {
	int node = 0;
	for(int j = 30; j >= 0; j--) {
		int bit = x >> j & 1;
		if(!trie[node][bit]) trie[node][bit] = ++idx;
		node = trie[node][bit];
		mn[node] = min(mn[node],i);
	}
}

int get(int tr,int x) {
	int node = 0,val = 0,res = inf;
	for(int j = 30; j >= 0; j--) {
		int bit = x >> j & 1;
		int bt = tr >> j & 1;
		if(bit > 0) {
			if(!trie[node][bit ^ bt]) break;
			node = trie[node][bit ^ bt];
			if(!j) res = min(res,mn[node]);
		}else {
			if(trie[node][bt ^ 1] > 0) res = min(res,mn[trie[node][bt ^ 1]]);
			if(!trie[node][bt]) break;
			node = trie[node][bt];
			if(!j) res = min(res,mn[node]);
		}
	}
	return res;
}
		 		 	 		 
signed main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
	
	int n,x;
	cin >> n >> x;
	for(int i = 1; i < N * 31 * 2; i++) mn[i] = inf;
	int l = n + 1,r = n;
	for(int i = 1; i <= n; i++) {
		cin >> a[i];
		pref[i] = a[i] ^ pref[i - 1];
		if(pref[i] >= x) {
			l = 1,r = i;
		}
		int L = get(pref[i],x);
		//cout << L << " " << i << " " << l << " " << r << endl;
		if(i - L + 1 > r - l + 1) {
			l = L;
			r = i;
		}else if(i - L + 1 == r - l + 1 && L < l) {
			l = L;
			r = i;
		}
		Add(pref[i],i + 1);
	}
	cout << l << " " << r - l + 1;
    return 0;
}

Compilation message (stderr)

xor.cpp: In function 'int get(int, int)':
xor.cpp:32:15: warning: unused variable 'val' [-Wunused-variable]
   32 |  int node = 0,val = 0,res = inf;
      |               ^~~

• Subtask 1: 100 / 100