結果

問題 No.2658 L-R Nim
ユーザー kotatsugame
提出日時 2024-03-01 22:04:16
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 6,484 ms / 7,000 ms
コード長 1,144 bytes
コンパイル時間 720 ms
コンパイル使用メモリ 72,524 KB
実行使用メモリ 10,108 KB
最終ジャッジ日時 2024-09-29 14:03:17
合計ジャッジ時間 132,047 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 5
other AC * 48
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include<iostream>
#include<vector>
#include<cassert>
using namespace std;
int N,K;
int A[50505];
bool Lf[50505],Rf[50505];
bool Le[1<<20],Re[1<<20];
int cnt[1<<20];
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	cin>>N>>K;
	for(int i=0;i<N;i++)cin>>A[i];
	{//L
		int now=0;
		Le[now]=true;
		for(int i=0;i<N;i++)
		{
			now^=A[i];
			Lf[i+1]=Lf[i]||Le[now];
			Le[now]=true;
		}
		if(!Lf[N])
		{
			cout<<"Yes\n";
			return 0;
		}
	}
	vector<int>L,R;
	R.reserve(N+1);
	L.reserve(N+1);
	{//R
		int now=0;
		Re[now]=true;
		R.push_back(now);
		for(int i=N;i--;)
		{
			now^=A[i];
			Rf[i]=Rf[i+1]||Re[now];
			Re[now]=true;
			R.push_back(now);
		}
	}
	L.push_back(0);
	for(int r:R)cnt[r]++;
	int ALL=R.back();
	for(int i=0;i<N;i++)
	{
		int r=R.back();R.pop_back();
		for(int l:L)cnt[l^r]--;
		if(!Lf[i]&&!Rf[i+1])
		{
			for(int x=1;x<=K;x++)if(cnt[ALL^A[i]^(A[i]+x)]==0)
			{
				cout<<"Yes\n";
				return 0;
			}
			for(int x=1;x<=min(K,A[i]-1);x++)if(cnt[ALL^A[i]^(A[i]-x)]==0)
			{
				cout<<"Yes\n";
				return 0;
			}
		}
		{
			int l=L.back()^=A[i];
			L.push_back(l);
			for(int r:R)cnt[l^r]++;
		}
	}
	cout<<"No\n";
}
0