답안 #91812

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
91812	2018-12-30T07:32:44 Z	SamAnd	XOR (IZhO12_xor)	C++17	100 / 100	1840 ms	15992 KB

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

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.0 / 100.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2 ms	376 KB	Output is correct
2	Correct	2 ms	376 KB	Output is correct
3	Correct	2 ms	376 KB	Output is correct
4	Correct	3 ms	376 KB	Output is correct
5	Correct	12 ms	1400 KB	Output is correct
6	Correct	26 ms	1656 KB	Output is correct
7	Correct	15 ms	1656 KB	Output is correct
8	Correct	16 ms	1784 KB	Output is correct
9	Correct	246 ms	6720 KB	Output is correct
10	Correct	261 ms	6644 KB	Output is correct
11	Correct	211 ms	6520 KB	Output is correct
12	Correct	244 ms	6520 KB	Output is correct
13	Correct	180 ms	6576 KB	Output is correct
14	Correct	218 ms	6640 KB	Output is correct
15	Correct	395 ms	6712 KB	Output is correct
16	Correct	173 ms	6520 KB	Output is correct
17	Correct	1436 ms	15896 KB	Output is correct
18	Correct	1239 ms	15992 KB	Output is correct
19	Correct	1840 ms	15992 KB	Output is correct
20	Correct	1022 ms	15908 KB	Output is correct