結果

問題 No.2658 L-R Nim
ユーザー kotatsugamekotatsugame
提出日時 2024-03-01 22:04:16
言語 C++14
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 6,584 ms / 7,000 ms
コード長 1,144 bytes
コンパイル時間 577 ms
コンパイル使用メモリ 72,124 KB
実行使用メモリ 10,104 KB
最終ジャッジ日時 2024-03-01 22:06:52
合計ジャッジ時間 133,288 ms
ジャッジサーバーID
（参考情報） 		judge12 / judge11
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
6,676 KB
testcase_01 AC 2 ms
6,676 KB
testcase_02 AC 2 ms
6,676 KB
testcase_03 AC 2 ms
6,676 KB
testcase_04 AC 2 ms
6,676 KB
testcase_05 AC 11 ms
9,760 KB
testcase_06 AC 149 ms
9,760 KB
testcase_07 AC 13 ms
9,760 KB
testcase_08 AC 135 ms
9,760 KB
testcase_09 AC 147 ms
9,764 KB
testcase_10 AC 146 ms
9,760 KB
testcase_11 AC 27 ms
9,764 KB
testcase_12 AC 145 ms
9,764 KB
testcase_13 AC 169 ms
9,760 KB
testcase_14 AC 149 ms
9,760 KB
testcase_15 AC 136 ms
9,760 KB
testcase_16 AC 152 ms
9,760 KB
testcase_17 AC 194 ms
9,764 KB
testcase_18 AC 152 ms
9,772 KB
testcase_19 AC 146 ms
9,760 KB
testcase_20 AC 28 ms
9,760 KB
testcase_21 AC 155 ms
9,760 KB
testcase_22 AC 152 ms
9,760 KB
testcase_23 AC 135 ms
9,760 KB
testcase_24 AC 66 ms
9,760 KB
testcase_25 AC 3,310 ms
9,988 KB
testcase_26 AC 3,611 ms
10,100 KB
testcase_27 AC 2,670 ms
9,988 KB
testcase_28 AC 3,370 ms
10,092 KB
testcase_29 AC 165 ms
9,992 KB
testcase_30 AC 75 ms
9,992 KB
testcase_31 AC 6,328 ms
10,032 KB
testcase_32 AC 6,174 ms
10,040 KB
testcase_33 AC 2,351 ms
10,104 KB
testcase_34 AC 5,991 ms
10,032 KB
testcase_35 AC 1,122 ms
6,676 KB
testcase_36 AC 6,480 ms
10,032 KB
testcase_37 AC 6 ms
6,676 KB
testcase_38 AC 6,448 ms
10,032 KB
testcase_39 AC 6,437 ms
10,032 KB
testcase_40 AC 6,464 ms
10,032 KB
testcase_41 AC 6,473 ms
10,032 KB
testcase_42 AC 6,509 ms
10,032 KB
testcase_43 AC 6,455 ms
10,032 KB
testcase_44 AC 6,555 ms
10,032 KB
testcase_45 AC 6,376 ms
10,032 KB
testcase_46 AC 6,377 ms
10,032 KB
testcase_47 AC 6,413 ms
10,032 KB
testcase_48 AC 2,858 ms
9,988 KB
testcase_49 AC 75 ms
9,992 KB
testcase_50 AC 6,417 ms
10,032 KB
testcase_51 AC 6,584 ms
10,032 KB
testcase_52 AC 6,510 ms
10,032 KB
権限があれば一括ダウンロードができます

ソースコード

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