結果

問題 No.2658 L-R Nim
ユーザー kotatsugamekotatsugame
提出日時 2024-03-01 22:04:16
言語 C++14
(gcc 12.3.0 + boost 1.83.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
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
6,820 KB
testcase_01 AC 2 ms
6,816 KB
testcase_02 AC 2 ms
6,816 KB
testcase_03 AC 2 ms
6,816 KB
testcase_04 AC 2 ms
6,816 KB
testcase_05 AC 11 ms
9,700 KB
testcase_06 AC 148 ms
9,616 KB
testcase_07 AC 12 ms
9,688 KB
testcase_08 AC 114 ms
9,584 KB
testcase_09 AC 147 ms
9,792 KB
testcase_10 AC 150 ms
9,748 KB
testcase_11 AC 27 ms
9,644 KB
testcase_12 AC 151 ms
9,584 KB
testcase_13 AC 151 ms
9,596 KB
testcase_14 AC 148 ms
9,804 KB
testcase_15 AC 133 ms
9,644 KB
testcase_16 AC 148 ms
9,776 KB
testcase_17 AC 153 ms
9,708 KB
testcase_18 AC 152 ms
9,660 KB
testcase_19 AC 152 ms
9,652 KB
testcase_20 AC 28 ms
9,668 KB
testcase_21 AC 152 ms
9,600 KB
testcase_22 AC 153 ms
9,588 KB
testcase_23 AC 133 ms
9,752 KB
testcase_24 AC 65 ms
9,580 KB
testcase_25 AC 3,143 ms
10,088 KB
testcase_26 AC 3,590 ms
9,980 KB
testcase_27 AC 2,556 ms
9,948 KB
testcase_28 AC 3,333 ms
10,096 KB
testcase_29 AC 142 ms
9,936 KB
testcase_30 AC 74 ms
10,000 KB
testcase_31 AC 6,266 ms
9,880 KB
testcase_32 AC 6,083 ms
9,876 KB
testcase_33 AC 2,306 ms
10,096 KB
testcase_34 AC 5,913 ms
10,108 KB
testcase_35 AC 1,073 ms
6,816 KB
testcase_36 AC 6,401 ms
10,044 KB
testcase_37 AC 6 ms
6,816 KB
testcase_38 AC 6,375 ms
10,056 KB
testcase_39 AC 6,484 ms
10,068 KB
testcase_40 AC 6,470 ms
10,064 KB
testcase_41 AC 6,433 ms
10,060 KB
testcase_42 AC 6,367 ms
10,072 KB
testcase_43 AC 6,452 ms
10,072 KB
testcase_44 AC 6,456 ms
10,036 KB
testcase_45 AC 6,408 ms
10,008 KB
testcase_46 AC 6,417 ms
9,956 KB
testcase_47 AC 6,374 ms
10,108 KB
testcase_48 AC 2,814 ms
9,948 KB
testcase_49 AC 75 ms
9,996 KB
testcase_50 AC 6,276 ms
10,008 KB
testcase_51 AC 6,351 ms
10,032 KB
testcase_52 AC 6,397 ms
9,964 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