Submission #537965

#	Time	Username	Problem	Language	Result	Execution time	Memory
537965		GioChkhaidze	XOR (IZhO12_xor)	C++14	0 / 100	1 ms	340 KiB

xor

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

const int N = 250005;

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

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

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

void upd(int idx, int id) {
	D[idx] = min(D[idx], ind);
	if (id == -1) return ;
	int 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);
		get(1, 30, 0);
		upd(1, 30);
	}
	cout << indx << " " << len << "\n";
}

Compilation message (stderr)

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

• Subtask 1: 0 / 100