Submission #225297

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
225297	2020-04-20T08:04:38 Z	cgiosy	XOR (IZhO12_xor)	C++17	100 / 100	163 ms	89208 KB

xor

#include <bits/stdc++.h>
using namespace std;

struct iii { int l, r, k; };
int main() {
	ios::sync_with_stdio(0);cin.tie(0);
	int N, M, K=0, m=0, id=1;
	cin>>N>>M;
	vector<iii> T(N*30, {0, 0, INT_MAX});
	for(int i=0, x=0; i<N;) {
		for(int p=1, d=30; d--;) {
			auto&[l,r,k]=T[p];
			if(x&1<<d) p=r=r?:++id;
			else p=l=l?:++id;
			T[p].k=min(T[p].k, i);
		}

		int j=++i, t;
		cin>>t; x^=t; t=0;
		for(int p=1, d=30; d-- && p;) {
			auto[l,r,k]=T[p];
			int a=x&1<<d, b=M&1<<d;
			if(!b) j=min(j, T[a?l:r].k);
			p=a^b ? r : l;
			t|=b;
			if(t>=M) { j=min(j, T[p].k); break; }
		}
		if(m<i-j) m=i-j, K=j+1;
	}
	cout<<K<<' '<<m;
}

Compilation message

xor.cpp: In function 'int main()':
xor.cpp:12:15: warning: unused variable 'k' [-Wunused-variable]
    auto&[l,r,k]=T[p];
               ^
xor.cpp:21:14: warning: unused variable 'k' [-Wunused-variable]
    auto[l,r,k]=T[p];
              ^

Subtask #1

100.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	5 ms	512 KB	Output is correct
2	Correct	5 ms	384 KB	Output is correct
3	Correct	5 ms	384 KB	Output is correct
4	Correct	5 ms	896 KB	Output is correct
5	Correct	16 ms	8448 KB	Output is correct
6	Correct	18 ms	10752 KB	Output is correct
7	Correct	19 ms	11136 KB	Output is correct
8	Correct	19 ms	12416 KB	Output is correct
9	Correct	67 ms	36344 KB	Output is correct
10	Correct	61 ms	36344 KB	Output is correct
11	Correct	59 ms	36344 KB	Output is correct
12	Correct	65 ms	36344 KB	Output is correct
13	Correct	69 ms	36344 KB	Output is correct
14	Correct	73 ms	36300 KB	Output is correct
15	Correct	58 ms	36344 KB	Output is correct
16	Correct	69 ms	36344 KB	Output is correct
17	Correct	154 ms	89208 KB	Output is correct
18	Correct	156 ms	89172 KB	Output is correct
19	Correct	160 ms	89208 KB	Output is correct
20	Correct	163 ms	89208 KB	Output is correct