Codeforces Round ＃765 (Div. 2) D. Binary Spiders

Any XOR greater than or equal to k

link ：Problem - D - Codeforces
The question ： Given n Number , Find the largest set , Make the XOR of any two numbers in the set greater than or equal to k, Find the largest set and output the subscript of the number in the set .

Answer key ： First , about $k$ highest $1$ Bits above , The XOR of any two higher bits that are different must be greater than $k$ Of , So you can put all the numbers in order first , From the highest to $k$ Highest bit enumeration , In this case, the numbers with different bit states during enumeration can be divided into two sets , How to choose the number in two sets will not make the number between two sets different or produce less than $k$ Number of numbers . But to $k$ be equal to $1$ when , The number in the current set can only be selected at most $2$ The number of current binary bits in different states ensures that the current bit XOR is $1$ , But even if XOR is $1$ There is no guarantee that greater than $k$, So we can traverse the maximum XOR number of each number in this interval , If there is more than $k$ Then choose these two numbers , If not, just choose one （ Only when the rest of the intervals have access to data, you can choose any one to ensure that the number exclusive or with the rest of the intervals is greater than or equal to $k$）. As for how to find the number with the largest XOR value between a number and a number in a certain interval , It can be persistent $01trie$ For maintenance , Of course, you can also build a tree for each searched interval $01trie$ , However, it is not recommended to build trees in search .

#pragma GCC optimize("Ofast") 
#pragma GCC optimize("unroll-loops")
#include<iostream>
#include<algorithm>
#include<vector>
#include<cstring>
#include<functional>
#include<queue>
#include<unordered_map>
#include<map>
#include<set>

using namespace std;
using ll=long long;
using P=pair<int,int>;
const ll inf=1e18;
const int maxn=3e5+5;

struct trie{
    
	int now=1;
	int t[maxn*40][2],val[maxn*40],ct[maxn*40],rt[maxn];
	inline void insert(int a,int b,int x,int y)
	{
    
		rt[b]=++now;
		int l=rt[a],r=rt[b];
		for(int i=30;i>=0;i--)
		{
    
			int p=x>>i&1;
			ct[r]=ct[l]+1;
			t[r][p^1]=t[l][p^1];
			t[r][p]=++now;
			l=t[l][p],r=t[r][p];
		}
		val[r]=y,ct[r]=ct[l]+1; return;
	}
	inline int query(int l,int r,int x,int k)
	{
    
		l=rt[l],r=rt[r];
		for(int i=30;i>=0;i--)
		{
    
			int p=x>>i&1;
			if(k>>i&1)
			{
    
				if(ct[t[r][p^1]]-ct[t[l][p^1]])
				{
    
					l=t[l][p^1],r=t[r][p^1];
				}
				else return 0;
			}
			else
			{
    
				if(ct[t[r][p^1]]-ct[t[l][p^1]])
				{
    
					r=t[r][p^1],l=t[l][p^1];
					for(int j=i-1;j>=0;j--)
					{
    
						if(ct[t[r][p^1]]-ct[t[l][p^1]])
						{
    
							r=t[r][p^1],l=t[l][p^1];
						}
						else
						{
    
							r=t[r][p],l=t[l][p];
						}
					}
					break;
				}
				else r=t[r][p],l=t[l][p];
			}
		}
		return val[r];
	}
}t;

void solve()
{
    
	int n,k; cin>>n>>k;
	vector<int>ans;
	vector<P>a(n+1);
	for(int i=1;i<=n;i++)
	{
    
		cin>>a[i].first,a[i].second=i;
	}
	sort(a.begin()+1,a.end());
	for(int i=1;i<=n;i++)
	{
    
		t.insert(i-1,i,a[i].first,a[i].second); 
	}
	
	function<void(int,int,int,int,bool)>dfs=[&](int l,int r,int sum,int dep,bool lim)
	{
    
		if(l>r)return;
		if(k>>dep&1)
		{
    
			int flag=0;
			for(int i=l;i<=r;i++)
			{
    
				int p=t.query(l-1,r,a[i].first,k);
				if(p)
				{
    
					ans.push_back(a[i].second);
					ans.push_back(p);  
					flag=1; break;
				}
			}
			if(!flag&&lim)ans.push_back(a[l].second);
		}
		else
		{
    
			int p=lower_bound(a.begin()+l,a.begin()+1+r,P(sum+(1<<dep),0))-a.begin();
			dfs(l,p-1,sum,dep-1,p<=r||lim);
			dfs(p,r,sum+(1<<dep),dep-1,l<p||lim);
		}
		return;
	};
	
	if(k)
	{
    
		dfs(1,n,0,30,0);
		if(!ans.size()&&a[n].first>=k)
		{
    
			ans.push_back(a[n].second);
		}
		if(ans.size())
		{
    
			cout<<ans.size()<<"\n";
			for(auto i:ans)cout<<i<<" ";
		}
		else cout<<-1;
	}
	else
	{
    
		cout<<n<<"\n";
		for(int i=1;i<=n;i++)cout<<i<<" ";
	}
	return;
}

int main()
{
    
	ios::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);
	int t=1; //cin>>t;
	while(t--)solve();
	return 0;
}