Submission #338660

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
338660	2020-12-23T15:28:58 Z	tengiz05	XOR (IZhO12_xor)	C++17	100 / 100	220 ms	58604 KB

xor

#include <bits/stdc++.h>
using namespace std;
//#define int long long
#define FASTIO ios_base::sync_with_stdio(false); cin.tie(NULL);
#define all(x) (x).begin(), (x).end()
#define pb push_back
#define pii pair<int, int>
#define ff first
#define ss second
#define PI acos(-1)
#define ld long double
template<class T> bool ckmin(T& a, const T& b) {return a>b? a=b, true:false;}
template<class T> bool ckmax(T& a, const T& b) {return a<b? a=b, true:false;}
const int mod = 1e9+7, N = 250005;
int msb(int val){return sizeof(int)*8-__builtin_clzll(val)-1;}
int a[N], n, m, k;
int pr[N];
struct node{
	array<node*,2> kids;
	int ans;
	node(){
		ans = n+1;
		kids = {NULL, NULL};
	}
};
void add(int i, int x, node* root, int ind){
	if(i<0)return;
	int bit = (x>>i)&1;
	if(root->kids[bit] == NULL)
		root->kids[bit] = new node();
	root = root->kids[bit];
	ckmin(root->ans, ind);
	add(i-1, x, root, ind);
}
int get(int i, int x, node *root, int cur){
	if(cur >= k)return root->ans;
	if(i<0 || cur+((1<<(i+1))-1) < k)return n+1;
	int res = n+1;
	int bit = (x>>i)&1;
	for(int j=0;j<2;j++)
		if(root->kids[j] != NULL)
			ckmin(res, get(i-1, x, root->kids[j], cur+((j!=bit)*(1<<i))));
	return res;
}
void solve(int test_case){
	int i, j;
	cin >> n >> k;
	for(i=1;i<=n;i++){
		cin >> a[i];
		pr[i] = a[i]^pr[i-1];
	}
	node* root = new node();
	int L = 1, R = 1;
	for(i=1;i<=n;i++){
		add(30, pr[i-1], root, i);
		int l = get(30, pr[i], root, 0);
		if(R-L < i-l)L=l,R=i;
	}
	cout << L << ' ' << R-L+1 << '\n';
	return;
}

signed main(){
	FASTIO;
#define MULTITEST 0
#if MULTITEST
	int _T;
	cin >> _T;
	for(int T_CASE = 1; T_CASE <= _T; T_CASE++)
		solve(T_CASE);
#else
	solve(1);
#endif
	return 0;
}

Compilation message

xor.cpp: In function 'void solve(int)':
xor.cpp:46:9: warning: unused variable 'j' [-Wunused-variable]
   46 |  int i, j;
      |         ^

Subtask #1

100.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	364 KB	Output is correct
2	Correct	1 ms	364 KB	Output is correct
3	Correct	1 ms	364 KB	Output is correct
4	Correct	1 ms	620 KB	Output is correct
5	Correct	8 ms	1900 KB	Output is correct
6	Correct	10 ms	2156 KB	Output is correct
7	Correct	10 ms	2156 KB	Output is correct
8	Correct	14 ms	2284 KB	Output is correct
9	Correct	84 ms	27648 KB	Output is correct
10	Correct	83 ms	27756 KB	Output is correct
11	Correct	83 ms	27628 KB	Output is correct
12	Correct	79 ms	27628 KB	Output is correct
13	Correct	85 ms	27628 KB	Output is correct
14	Correct	91 ms	27756 KB	Output is correct
15	Correct	82 ms	27628 KB	Output is correct
16	Correct	81 ms	27628 KB	Output is correct
17	Correct	220 ms	58476 KB	Output is correct
18	Correct	216 ms	58604 KB	Output is correct
19	Correct	213 ms	58476 KB	Output is correct
20	Correct	219 ms	58476 KB	Output is correct