제출 #721248

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
721248		nishkarsh	XOR (IZhO12_xor)	C++14	100 / 100	281 ms	26148 KiB

xor

#include <bits/stdc++.h>
#define ll long long
#define ull unsigned long long
#define pb push_back
#define mp make_pair
#define F first
#define S second
#define pii pair<int,int>
#define pll pair<ll,ll>
#define pcc pair<char,char>
#define vi vector <int>
#define vl vector <ll>
#define sd(x) scanf("%d",&x)
#define slld(x) scanf("%lld",&x)
#define pd(x) printf("%d",x)
#define plld(x) printf("%lld",x)
#define pds(x) printf("%d ",x)
#define pllds(x) printf("%lld ",x)
#define pdn(x) printf("%d\n",x)
#define plldn(x) printf("%lld\n",x)
using namespace std;
ll powmod(ll base,ll exponent,ll mod){
	ll ans=1;
	if(base<0) base+=mod;
	while(exponent){
		if(exponent&1)ans=(ans*base)%mod;
		base=(base*base)%mod;
		exponent/=2;
	}
	return ans;
}
ll gcd(ll a, ll b){
	if(b==0) return a;
	else return gcd(b,a%b);
}
const int INF = 2e9;
const ll INFLL = 4e18;
const int upperlimit = 2e3+1;
const int mod = 1e9+7;
const int bits = 30;
struct trie_node{
	int nxt[2];
	int min_ind;
	trie_node(){
		nxt[0] = 0;
		nxt[1] = 0;
		min_ind = INF;
	}
};
struct bin_trie{
	vector<trie_node> trie;
	int nodes = 1;
	bool bin[bits];
	bin_trie(){
		trie.resize(1);
	}
	void add_num(int x,int ind){
		int cur_node = 0;
		for(int i = 0; i < bits; i++) bin[i] = x&(1<<i);
		for(int i = bits-1; i >= 0; i--){
			if(! trie[cur_node].nxt[bin[i]]){
				trie[cur_node].nxt[bin[i]] = nodes++;
				trie.emplace_back();
			}
			cur_node = trie[cur_node].nxt[bin[i]];
			trie[cur_node].min_ind = min(trie[cur_node].min_ind,ind);
		}
	}
	int min_index(int curr_xor, int req_xor){
		int ans = INF;
		int cur_node = 0;
		int x = curr_xor ^ req_xor;
		for(int i = 0; i < bits; i++) bin[i] = x&(1<<i);
		for(int i = bits-1; i >= 0; i--){
			if(! (req_xor&(1<<i))) if(trie[cur_node].nxt[bin[i]^1]) ans = min(ans,trie[trie[cur_node].nxt[bin[i]^1]].min_ind);
			if(! trie[cur_node].nxt[bin[i]]) return ans;
			cur_node = trie[cur_node].nxt[bin[i]];
			if(i==0) ans = min(ans,trie[cur_node].min_ind);
		}
		return ans;
	}
};
int main() {
	int n,x,y,pre = 0,len = 0,lt = 1,quer;
	cin >> n >> x;
	bin_trie T;
	T.add_num(0,0);
	for(int i = 1; i <= n; i++){
		cin >> y;
		pre ^= y;
		quer = T.min_index(pre,x);
		if(len < i-quer){
			len = i-quer;
			lt = quer+1;
		}
		T.add_num(pre,i);
	}
	cout << lt << " " << len;
	return 0;
}

• Subtask 1: 100 / 100