Submission #91812

#	Time	Username	Problem	Language	Result	Execution time	Memory
91812		SamAnd	XOR (IZhO12_xor)	C++17	100 / 100	1840 ms	15992 KiB

xor

#include <iostream>
#include <algorithm>
#include <vector>
#include <cmath>
#include <map>
using namespace std;
const int N=1000000,M=31;

int a[N], p[N], n;
int x, y, b, t;
int xx[M], yy[M];
int ansx=0,ansy=-1;
void erk()
{
	int i = 0;
	while(x || i < 30)
	{
		xx[i] = x % 2;
		++i;
		x /= 2;
	}
	reverse(xx, xx + M);
}
void ubd()
{
	map<int,int> mp;
	for(int i=0;i<=n;++i)
	{
		int mn = p[i]&b^y&b;
		if(mp.find(mn)!=mp.end() && (i-mp[mn]>ansy-ansx || (i-mp[mn]==ansy-ansx && i<ansx)))
		{
			ansx=mp[mn];
			ansy=i;
		}
		if(mp.find(p[i]&b)==mp.end())
			mp[p[i]&b]=i;
	}
	///
}
int main()
{
	//freopen("c.in","r",stdin);
	//freopen("c.out","w",stdout);
	//in
	scanf("%d%d",&n,&x);
	for(int i=1;i<=n;++i)
		scanf("%d",&a[i]);
	for(int i=1;i<=n;++i)
		p[i]=p[i-1]^a[i];
	////
	t=1;
	for(int i=0;i<M;++i)
		t*=2;
	--t;
	erk();
	////
	bool z=false;
	for(int i=0;i<M;++i)
	{
		b|=(1<<(M-1-i));
		if(xx[i]==0)
		{
			yy[i]=1;
			y|=(1<<(M-1-i));
			ubd();
			yy[i]=0;
			y^=(1<<(M-1-i));
		}
		else
		{
			z=true;
			yy[i]=1;
			y|=(1<<(M-1-i));
		}
		if(!z)
			b^=(1<<(M-1-i));
	}
	ubd();
	////
	cout<<ansx+1<<' '<<(ansy-(ansx+1)+1)<<endl;
//	system("pause");
	return 0;
}

Compilation message (stderr)

xor.cpp: In function 'void ubd()':
xor.cpp:29:16: warning: suggest parentheses around arithmetic in operand of '^' [-Wparentheses]
   int mn = p[i]&b^y&b;
            ~~~~^~
xor.cpp: In function 'int main()':
xor.cpp:45:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d%d",&n,&x);
  ~~~~~^~~~~~~~~~~~~~
xor.cpp:47:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d",&a[i]);
   ~~~~~^~~~~~~~~~~~

• Subtask 1: 100 / 100