結果
問題 | No.2658 L-R Nim |
ユーザー |
|
提出日時 | 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 |
ソースコード
#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"; }