Submission #683849

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
683849	2023-01-19T13:31:12 Z	vovamr	XOR (IZhO12_xor)	C++17	100 / 100	129 ms	46624 KB

xor

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define fi first
#define se second
#define ll long long
#define ld long double
#define sz(x) ((int)(x).size())
#define all(x) 	(x).begin(), (x).end()
#define pb push_back
#define mpp make_pair
#define ve vector
using namespace std;
using namespace __gnu_pbds;
template<class T> using oset = tree<T,null_type,less<T>,rb_tree_tag,tree_order_statistics_node_update>;
const ll inf = 1e18; const int iinf = 1e9;
typedef pair<ll, ll> pll;
typedef pair<int, int> pii;
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
template <typename T> inline bool chmin(T& a, T b) { return (a > b ? a = b, 1 : 0); }
template <typename T> inline bool chmax(T& a, T b) { return (a < b ? a = b, 1 : 0); }

pii answer = {-1, -1};

const int N = 2.5e5 * 30 + 100;
int w = 0;

int ch[N][2];
int mn[N];

inline void add(const int &x, const int &id) {
	int v = 0;
	for (int i = 29; ~i; --i) {
		int b = x >> i & 1;
		if (!ch[v][b]) ch[v][b] = ++w;
		
		chmin(mn[v], id);
		v = ch[v][b];
	}
	chmin(mn[v], id);
}

inline void relax(const int &x, const int &need, const int &id) {
	int v = 0, ok = 1;
	for (int i = 29; ~i; --i) {
		int b = (x ^ need) >> i & 1;
		int tr = need >> i & 1;

		if (ch[v][b ^ 1] && !tr) {
			int ps = mn[ch[v][b ^ 1]];
			chmax(answer, mpp(id - ps, -(ps + 1)));
		}

		if (!ch[v][b]) {
			ok = 0;
			break;
		}
		v = ch[v][b];
	}
	if (ok) {
		int ps = mn[v];
		chmax(answer, mpp(id - ps, -(ps + 1)));
	}
}

inline void solve() {
	for (int i = 0; i < N; ++i) mn[i] = iinf;

	int n, x;
	cin >> n >> x;

	ve<int> a(n);
	for (auto &i : a) cin >> i;

	int xr = 0;
	for (int i = 0; i < n; ++i) {

		xr ^= a[i];
		if (xr >= x) {
			chmax(answer, mpp(i + 1, -0));
		}

		relax(xr, x, i);
		add(xr, i);
	}

	cout << -answer.se + 1 << " " << answer.fi;
}

signed main() {
	ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
	int q = 1; // cin >> q;
	while (q--) solve();
	cerr << fixed << setprecision(3) << "Time execution: " << (double)clock() / CLOCKS_PER_SEC << endl;
}

Subtask #1

100.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	25 ms	29692 KB	Output is correct
2	Correct	19 ms	29664 KB	Output is correct
3	Correct	24 ms	29652 KB	Output is correct
4	Correct	21 ms	29656 KB	Output is correct
5	Correct	24 ms	30200 KB	Output is correct
6	Correct	24 ms	30292 KB	Output is correct
7	Correct	30 ms	30332 KB	Output is correct
8	Correct	34 ms	30352 KB	Output is correct
9	Correct	48 ms	37452 KB	Output is correct
10	Correct	62 ms	37380 KB	Output is correct
11	Correct	58 ms	37384 KB	Output is correct
12	Correct	51 ms	37448 KB	Output is correct
13	Correct	71 ms	37432 KB	Output is correct
14	Correct	63 ms	37488 KB	Output is correct
15	Correct	65 ms	37376 KB	Output is correct
16	Correct	52 ms	37428 KB	Output is correct
17	Correct	124 ms	46560 KB	Output is correct
18	Correct	129 ms	46620 KB	Output is correct
19	Correct	127 ms	46604 KB	Output is correct
20	Correct	110 ms	46624 KB	Output is correct