제출 #1224756

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1224756		tkm_algorithms	XOR (IZhO12_xor)	C++20	0 / 100	0 ms	320 KiB

xor

/**
*    In the name of Allah
*    We are nothing and you're everything
*    Ya Muhammad!
**/
#include <bits/stdc++.h>
 
using namespace std;
using ll = long long;
using ull = uint64_t;
 
#define all(x) begin(x), end(x)
#define sz(x) (int)(x).size()
//#define int long long
 
const char nl = '\n';
const int N = 2e5+5;
const int LOG = 30;
const ll inf = 0x3f3f3f3f3f3f3f3fll;

int tree[N*LOG][2];
int ind;

int mn[N*LOG][2], par[N*LOG][2];

void add(int x, int j) {
	int cur = 0;
	for (int i = LOG-1; i >= 0; --i) {
		int bit = (x>>i)&1;
		if (!tree[cur][bit]) {
			tree[cur][bit] = ++ind;
			mn[tree[cur][bit]][bit] = j;
		}
		cur = tree[cur][bit];
	}
}

int get(int x) {
	int res = N;
	int cur = 0;
	int last = 0;
	for (int i = LOG-1; i >= 0; --i) {
		int bit = (x>>i)&1;
		last = bit;
		if (bit == 1) {
			if (!tree[cur][bit])return res;
		} else {
			if (tree[cur][1] > 0)res = min(res, mn[tree[cur][1]][1]);
			if (!tree[cur][bit])return res;
		}
		//if (x == 0 && res == 1)cout << i << nl;
		if (i == 0)res = min(res, mn[tree[cur][bit]][bit]);
		cur = tree[cur][bit];
	}
	//res = min(res, mn[cur][last]);
	return res;
}


void solve() {
	int n, x; cin >> n >> x;
	add(0, 0);
	int xx = 0;
	int ans = -1, ans2;
	for (int i = 1; i <= n; ++i) {
		int a; cin >> a;
		xx ^= a;
		int val = get(x);
		if (xx >= x) {
			if (i > ans)ans = i, ans2 = 1;
		}
		//if (i == 1)cout << val << nl;
		if (i-val > ans) {
			//cout << val << nl;
			//cout << xx << nl;
			ans = i-val;
			ans2 = val+1;
		}
		add(xx, i);
	}
	
	if (ans == -1)cout << "-1";
	else cout << ans2 << " " << ans;
}

int32_t main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    solve();
  return 0;
}

• Subtask 1: 0 / 100