제출 #16855

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
16855		murat	XOR (IZhO12_xor)	C++98	90 / 100	153 ms	81800 KiB

xor

#include <bits/stdc++.h>

using namespace std;

#define dbgs(x) cerr << (#x) << " --> " << (x) << ' '
#define dbg(x) cerr << (#x) << " --> " << (x) << endl

#define foreach(i,x) for(type(x)i=x.begin();i!=x.end();i++)
#define FOR(ii,aa,bb) for(int ii=aa;ii<=bb;ii++)
#define ROF(ii,aa,bb) for(int ii=aa;ii>=bb;ii--)

#define type(x) __typeof(x.begin())

#define orta (bas + son >> 1)
#define sag (k + k + 1)
#define sol (k + k)

#define pb push_back
#define mp make_pair

#define nd second
#define st first

#define endl '\n'

typedef pair < int ,int > pii;

typedef long long ll;

const long long linf = 1e18+5;
const int mod = (int) 1e9 + 7;
const int logN = 17;
const int inf = 1e9;
const int N = 250001;

int F[N << 4], S = 1, mx[N << 4], mn[N << 4], t, n, m, x, y, z, a[N], b[N], way[N << 4][2];

void insert(int x, int index) {
	int node = 1;
	ROF(i, 29, 0) {
		int t = (1 << i) & x;
		t = t != 0;
		if(!way[node][t]) way[node][t] = ++S;
		node = way[node][t];
	} F[node] = max(F[node], index); 
}

pii dfs(int node) {
	mn[node] = inf;
	if(way[node][0]) {
		pii temp = dfs(way[node][0]);
		mx[node] = max(mx[node], temp.st);	
		mn[node] = min(mn[node], temp.nd);	
	}
	if(way[node][1]) {
		pii temp = dfs(way[node][1]);
		mx[node] = max(mx[node], temp.st);	
		mn[node] = min(mn[node], temp.nd);	
	}
	if(mx[node] == 0) 
		mx[node] = mn[node] = F[node];
	return mp(mx[node], mn[node]);
}

int solve(int node, int d, int y) {
	if(d == 0) return mx[node];
	if((x & (1 << d)) && (y & (1 << d))) {
		if(way[node][0]) return solve(way[node][0], d-1, y);
		else return 0;
	}

	if(y & (1 << d)) { 
		if(way[node][1]) return max(solve(way[node][1], d-1, y), mx[way[node][0]]);
		else return mx[way[node][0]];
	}
	if(x & (1 << d)) {
		if(way[node][1]) return solve(way[node][1], d-1, y);
		else return 0;
	}
	if(way[node][0])
		return solve(way[node][0], d-1, y);
	else return 0;
}

int main() {
	scanf("%d %d",&n, &x);
	FOR(i, 1, n) {
		scanf("%d", &a[i]); 
		b[i] = a[i] ^ b[i-1];
		insert(b[i], i);
	}
	dfs(1);
	FOR(i, 1, n) {
		t = max(t, solve(1, 29, b[i]) - i);
	}
	FOR(i, 0, n-t)
		if((b[i+t] ^ b[i]) >= x) {
			cout << i + 1 << ' ' << t << endl;
			return 0;
		}
	return 0;
}

• Subtask 1: 90 / 100