Submission #537974

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
537974	2022-03-16T01:18:31 Z	GioChkhaidze	XOR (IZhO12_xor)	C++14	100 / 100	222 ms	31320 KB

xor

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

const int N = 250005;

int n, x, vl, ind, len = -1, indx, sz = 1;
int s[N], D[60 * N], T[60 * N][3];

inline void rec(int id) {
	if (len < ind - id || (len == ind - id && id + 1 < indx)) {
		len = ind - id, indx = id + 1;
	}
}

inline void get(int idx, int id, int sum) {
	if (id == -1) { if (sum >= x) rec(D[idx]); return ; }
	bool t0 = ((vl >> id) & 1), t1 = (t0 ^ 1);
	if (T[idx][t1] && sum + (1 << id) > x) rec(D[T[idx][t1]]);	
	if (T[idx][t1] && sum + (1 << id) <= x) {
		get(T[idx][t1], id - 1, sum + (1 << id));
	}
		else
	if (T[idx][t0]) {
		get(T[idx][t0], id - 1, sum);
	}
}

inline void upd(int idx, int id) {
	D[idx] = min(D[idx], ind);
	if (id == -1) return ;
	bool t = ((vl >> id) & 1);
	if (!T[idx][t]) {
		T[idx][t] = ++sz;
		D[sz] = 1e9;
	}
	upd(T[idx][t], id - 1);
}

main () {
	ios::sync_with_stdio(false);
	cin.tie(NULL), cout.tie(NULL);
	D[1] = 1e9;
	cin >> n >> x;
	for (int i = 1; i <= n; ++i) {
		int y;
		cin >> y;
		s[i] = (s[i - 1] ^ y);
		ind = i, vl = s[i];
		if (s[i] >= x) rec(0);
		upd(1, 30), get(1, 30, 0);
	}
	cout << indx << " " << len << "\n";
}

Compilation message

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

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	1 ms	340 KB	Output is correct
4	Correct	1 ms	468 KB	Output is correct
5	Correct	9 ms	1236 KB	Output is correct
6	Correct	11 ms	1364 KB	Output is correct
7	Correct	12 ms	1396 KB	Output is correct
8	Correct	13 ms	1444 KB	Output is correct
9	Correct	67 ms	14636 KB	Output is correct
10	Correct	69 ms	14816 KB	Output is correct
11	Correct	71 ms	14592 KB	Output is correct
12	Correct	66 ms	14724 KB	Output is correct
13	Correct	69 ms	14708 KB	Output is correct
14	Correct	69 ms	14744 KB	Output is correct
15	Correct	68 ms	14668 KB	Output is correct
16	Correct	68 ms	14700 KB	Output is correct
17	Correct	220 ms	31204 KB	Output is correct
18	Correct	208 ms	31240 KB	Output is correct
19	Correct	222 ms	31292 KB	Output is correct
20	Correct	213 ms	31320 KB	Output is correct