Submission #869763

#	Time	Username	Problem	Language	Result	Execution time	Memory
869763		Firas_Briki	XOR (IZhO12_xor)	C++17	100 / 100	217 ms	101756 KiB

xor

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp> // Common file
#include <ext/pb_ds/tree_policy.hpp> // Including tree_order_statistics_node_update
using namespace std;
using namespace __gnu_pbds;
// #ifndef ONLINE_JUDGE
// #include "debug.cpp"
// #else
// #define dbg(...)
// #endif
#define endl "\n"
#define FAST ios_base::sync_with_stdio(false); cin.tie(NULL);
#define ll long long
#define pb(n) push_back(n)
#define F first
#define S second
#define mp(x, y) make_pair(x, y)
#define yes cout << "YES" << endl;
#define no cout << "NO" << endl;
#define nop cout << -1 << endl;
#define ordered_set tree<pair<int, int>, null_type, less<pair<int, int>>, rb_tree_tag, tree_order_statistics_node_update>
const ll sup = 1e18;
const ll inf = -1e18;
const ll mod = 1e9 + 7;
const int N_Max = 3e5 + 7;
const int Nax = 15;
const int LOG = 18;
const int BITS = 30;
const int ALPHA = 26;
ll gcd(ll a , ll b) {return b ? gcd(b , a % b) : a;}
ll lcm(ll a , ll b) {return (a * b) / gcd(a , b);}
ll inv(ll N) {if (N == 1) return 1; return (mod - ((mod / N) * inv(mod % N)) % mod) % mod;}

int nxt[30 * N_Max][2], mn[30 * N_Max][2];
int a[N_Max], pref[N_Max];
map<int, int> mp;
int N, x, cnt = 1;

int nxt_node(){
	return ++cnt;
}

void ins(int val, int ind){
	int curr = 1;
	for (int i = 30; i >= 0; i--){
		int c = (val >> i) & 1;
		if (nxt[curr][c] == -1){
			mn[curr][c] = ind;
			nxt[curr][c] = nxt_node();
		}
		mn[curr][c] = min(mn[curr][c], ind);
		curr = nxt[curr][c];
	}
}

int query(int val){
	int ret = 2e9, curr = 1;
	for (int i = 30; i >= 0; i--){
		if (curr == -1) break;
		int c = (val >> i) & 1, v = (x >> i) & 1;
		if (!v && nxt[curr][c ^ 1] != -1)
			ret = min(ret, mn[curr][c ^ 1]);
		if (v) curr = nxt[curr][c ^ 1];
		else curr = nxt[curr][c];
	}
	return ret;
}

void solve(){
	cin >> N >> x;
	memset(nxt, -1, sizeof(nxt));
	for (int i = 1; i <= N; i++) cin >> a[i];
	for (int i = 1; i <= N; i++) pref[i] = pref[i - 1] ^ a[i];
	pair<int, int> ans = {0, 0};
	for (int r = 1; r <= N; r++){
		ins(pref[r - 1], r);
		if (!mp.count(pref[r - 1])) mp[pref[r - 1]] = r;
		int l = query(pref[r]), val = x ^ pref[r];
		if (mp.count(val)) l = min(l, mp[val]);
		if (l == 2e9) continue;
		if (r - l + 1 > ans.S) ans = {l, r - l + 1};
		else if (r - l + 1 == ans.S) ans.F = min(ans.F, l);
	}
	assert(ans.F != 0);
	cout << ans.F << " " << ans.S << endl;
}

int main(){
    FAST
    // #ifndef ONLINE_JUDGE
    // freopen("input.txt","r",stdin);
    // freopen("output.txt","w",stdout);
    // #endif
    int tc = 1;
    // cin >> tc;
    while (tc--) solve();
    return 0;
}

• Subtask 1: 100 / 100