Submission #680010

#	Time	Username	Problem	Language	Result	Execution time	Memory
680010		pragmatist	XOR (IZhO12_xor)	C++17	100 / 100	111 ms	25160 KiB

xor

/*
#pragma comment(linker, "/stack:200000000")
#pragma GCC optimize("O3")
#pragma GCC target ("avx2")
#pragma GCC optimize("Ofast")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#pragma GCC optimize("unroll-loops")
#pragma GCC target("avx2", "bmi", "bmi2", "lzcnt", "popcnt")
*/

#include<bits/stdc++.h>
 
#define sz(v) (int)v.size()
#define ll long long
#define pb push_back
#define x first
#define y second
#define all(v) v.begin(), v.end()
#define rall(v) v.rbegin(), v.rend()
#define nl "\n"

using namespace std;
using pii = pair<int, int>;

const int N = (int)25e4 + 7; // make sure this is right
const int M = (int)2e6 + 7;
const int inf = (int)1e9 + 7;
const ll INF = (ll)3e18 + 7; 
const ll MOD = (ll)998244353; // make sure this is right

bool bit(int x, int i) {
	return x >> i & 1;
}

int sum(int x, int y) {
	x += y;
	if(x >= MOD) x -= MOD;
	return x;
}

pii dir[] = {{1, 0}, {0, 1}, {-1, 0}, {0, -1}};

int n, k, p[N];
int sz, t[M][2], mn[M];

void add(int mask, int val) {
	int v = 0;
	for(int i = 29; i >= 0; --i) {
		int x = bit(mask, i);
		if(!t[v][x]) {
			t[v][x] = ++sz;
		}  
		v = t[v][x];
		mn[v] = min(mn[v], val);
	}
}

int get(int mask) {
	int v = 0, res = inf;
	bool was = 1;
	for(int i = 29; i >= 0; --i) {
		int x = bit(k, i), y = bit(mask, i), c = 1 - y;
		if(x == 1) {
			if(!t[v][c]) {
				was = 0;
				break;
			}
	    	v = t[v][c];
		} else {
			res = min(res, mn[t[v][c]]);
			if(!t[v][y]) {
			    was = 0;
				break;
			}
	    	v = t[v][y]; 			
		}
	}
	if(was) res = min(res, mn[v]);
	return res;
}

void solve() {
	cin >> n >> k;
	fill(mn, mn + M, inf);
	for(int i = 1; i <= n; ++i) {
		cin >> p[i];
		p[i] ^= p[i - 1];
	}
	int L = 0, R = -1;
	add(0, 0);
	for(int i = 1; i <= n; ++i) {
		int j = get(p[i]);          
		if(i - j > R - L + 1) {
			L = j + 1, R = i;	
		}
		add(p[i], i);
	}
	cout << L << ' ' << R - L + 1;
}

signed main() {	
	ios_base::sync_with_stdio(0);
	cin.tie(0); 
	//freopen("c.in", "r", stdin);
	//freopen("c.out", "w", stdout);
	int test = 1;
	//cin >> test;
	for(int i = 1; i <= test; ++i) {
	 	//cout << "Case #" << i << ": ";
		solve();
	}
	return 0;
}

• Subtask 1: 100 / 100