Submission #1101247

#	Time	Username	Problem	Language	Result	Execution time	Memory
1101247		nightwing_808	XOR (IZhO12_xor)	C++17	100 / 100	97 ms	47428 KiB

xor

#include <bits/stdc++.h>
#define fastread() ios_base::sync_with_stdio(false), cin.tie(NULL), cout.tie(NULL)
#define nl "\n"
#define ll long long
#define all(x) x.begin(), x.end()
#define ff first
#define ss second
using namespace std;
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
template <typename T> using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
template <typename T> using ordered_multiset = tree<T, null_type, less_equal<T>, rb_tree_tag, tree_order_statistics_node_update>;
const int N=3e6+7,M=1e9+7;
const double pi=acos(-1.0);
struct vertex
{
	int flag,child[2],idx;
	vertex()
	{
		flag=0;
		idx=M;
		for (int i=0;i<2;i++) child[i]=-1;
	}
};
vertex Trie[N];
int avail=1;
void insert(int cur,int i,int num,int id)
{
	if (i<0)
	{
		Trie[cur].flag=1;
		return;
	}
	int x=(num>>i)&1;
	if (Trie[cur].child[x]==-1)
	{
		Trie[cur].child[x]=avail;
		Trie[avail]=vertex();
		avail++;
	}
	insert(Trie[cur].child[x],i-1,num,id);
	Trie[Trie[cur].child[x]].idx=min(Trie[Trie[cur].child[x]].idx,id);
	//cout<<num<<" "<<Trie[cur].idx<<nl;
}
int query(int num,int k)
{
	int cur=0,ans=M;
	for (int i=31;i>=0;i--)
	{
		int x=(num>>i)&1;
		int y=(k>>i)&1;
		if (x==y)
		{
			if (x==0)
			{
				bool f=0;
				if (Trie[cur].child[1]!=-1)
				{
					f=1;
					ans=min(ans,Trie[Trie[cur].child[1]].idx);
				}
				else if (Trie[cur].child[0]!=-1)
				{
					cur=Trie[cur].child[0];
				}
				else return M;
			}
			else
			{
				if (Trie[cur].child[0]!=-1)
				{
					cur=Trie[cur].child[0];
				}
				else return M;
			}
		}
		else
		{
			if (x==0)
			{
				if (Trie[cur].child[1]!=-1)
				{
					cur=Trie[cur].child[1];
				}
				else return M;
			}
			else
			{
				bool f=0;
				if (Trie[cur].child[0]!=-1)
				{
					f=1;
					ans=min(ans,Trie[Trie[cur].child[0]].idx);
				}
				else if (Trie[cur].child[1]!=-1)
				{
					cur=Trie[cur].child[1];
				}
				else return M;
			}
		}
	}
	ans=min(ans,Trie[cur].idx);
	return ans+1;
}
int main()
{
	fastread();
	if (fopen("input.in","r")) 
	{
		freopen("input.in","r",stdin);
		freopen("output.out","w",stdout);
	}
    int t=1;
    //cin>>t;
    for (int tc=1;tc<=t;tc++)
    {
    	int n,k;
    	cin>>n>>k;
    	int xo=0,ans=0,st=n+1;
    	Trie[0]=vertex();
    	avail=1;
    	insert(0,31,0,0);
    	for (int i=1;i<=n;i++)
    	{
    		int x;
    		cin>>x;
    		xo^=x;
    		int mn=query(xo,k);
    		if (i-mn+1>ans)
    		{
    			ans=i-mn+1;
    			st=mn;
    		}
    		insert(0,31,xo,i);
    	}
    	cout<<st<<" "<<ans<<nl;
    }
}

Compilation message (stderr)

xor.cpp: In function 'int query(int, int)':
xor.cpp:57:10: warning: variable 'f' set but not used [-Wunused-but-set-variable]
   57 |     bool f=0;
      |          ^
xor.cpp:90:10: warning: variable 'f' set but not used [-Wunused-but-set-variable]
   90 |     bool f=0;
      |          ^
xor.cpp: In function 'int main()':
xor.cpp:112:10: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  112 |   freopen("input.in","r",stdin);
      |   ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
xor.cpp:113:10: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  113 |   freopen("output.out","w",stdout);
      |   ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 100 / 100