Submission #588883

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
588883	2022-07-04T06:56:00 Z	fuad27	XOR (IZhO12_xor)	C++17	100 / 100	179 ms	60608 KB

xor

/*
 * Created: 2022-07-04 10:04
*/
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

using namespace __gnu_pbds;
using namespace std;
using namespace chrono;
// using namespace atcoder

template <typename T>
using ordered_set =
    tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;

typedef long long ll;
typedef long double ld;
const ll inf = 1e18;

#define pii		pair<int,int>
#define pll		pair<ll,ll>
#define vi		vector<int>
#define vll		vector<ll>
#define rep(i, a, b)	for(int i = (a);i<(b);i++)
#define repn(i, a, b)	for(int i = (a);i>=(b);i--)
#define ss		second
#define ff		first
#define mkp		make_pair
#define pb		push_back

#define all(x)		(x).begin(), (x).end()
struct node {
	node* child[2];
	ll idx;
	node() {
		child[0]=child[1]=nullptr;
		idx=inf;
	}
};
void insert(node*& root, ll a,ll idx, int bit) {
	if(root==nullptr) {
		root = new node();
	}
	root->idx=min(root->idx,idx);
	if(bit == -1)return;
	if((a&(1ll<<bit))) {
		insert(root->child[1], a,idx, bit-1);
	}
	else {
		insert(root->child[0], a, idx, bit-1);
	}
}
long long find(node*& root, ll a, ll x, int bit) {
	if(root==nullptr) {
		return inf;
	}
	if(bit == -1)return root->idx;
	if(x == 0)return root->idx;
	if(((1ll<<bit)&a)) {
		if(((1ll<<bit)&x)) {
			return find(root->child[0], a, x, bit-1);
		}
		else {
			return min(find(root->child[1],a, x, bit-1), find(root->child[0], 0, 0, bit-1));
		}
	}
	else {
		if(((1ll<<bit)&x)) {
			return find(root->child[1], a, x, bit-1);
		}
		else {
			return min(find(root->child[1], 0, 0, bit-1), find(root->child[0], a, x, bit-1));
		}
	}
}
void solve() {
	int n;
	ll x;
	cin >> n >> x;
	ll pref[n+1];
	pref[0]=0;
	rep(i, 0, n) {
		ll a;cin >> a;
		pref[i+1]=(pref[i]^a);
	}
	ll l=-1,r=-2;
	node* root=nullptr;
	rep(i, 0, n+1) {
		ll idx = find(root, pref[i], x, 30);
		insert(root, pref[i], i, 30);
		if(i-idx > r-l) {
			l=idx;
			r=i;
		}	
	}
	cout << l+1 << " " << (r-l) << "\n";
}

int main () {
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	int t = 1;
	while(t--) {
		solve();
	}
	return 0;
}

Subtask #1

100.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	340 KB	Output is correct
2	Correct	1 ms	340 KB	Output is correct
3	Correct	0 ms	340 KB	Output is correct
4	Correct	1 ms	468 KB	Output is correct
5	Correct	7 ms	1832 KB	Output is correct
6	Correct	9 ms	1972 KB	Output is correct
7	Correct	7 ms	2004 KB	Output is correct
8	Correct	9 ms	2132 KB	Output is correct
9	Correct	60 ms	27524 KB	Output is correct
10	Correct	75 ms	28416 KB	Output is correct
11	Correct	67 ms	28176 KB	Output is correct
12	Correct	59 ms	28316 KB	Output is correct
13	Correct	59 ms	28364 KB	Output is correct
14	Correct	66 ms	28428 KB	Output is correct
15	Correct	64 ms	28336 KB	Output is correct
16	Correct	81 ms	28256 KB	Output is correct
17	Correct	152 ms	60220 KB	Output is correct
18	Correct	179 ms	60304 KB	Output is correct
19	Correct	175 ms	60608 KB	Output is correct
20	Correct	170 ms	60280 KB	Output is correct