Submission #537974

#	Time	Username	Problem	Language	Result	Execution time	Memory
537974		GioChkhaidze	XOR (IZhO12_xor)	C++14	100 / 100	222 ms	31320 KiB

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 (stderr)

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

• Subtask 1: 100 / 100