結果
問題 | No.1242 高橋君とすごろく |
ユーザー |
![]() |
提出日時 | 2020-10-02 22:59:35 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 2 ms / 2,000 ms |
コード長 | 1,404 bytes |
コンパイル時間 | 806 ms |
コンパイル使用メモリ | 99,336 KB |
実行使用メモリ | 5,376 KB |
最終ジャッジ日時 | 2024-07-20 02:50:38 |
合計ジャッジ時間 | 1,957 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 4 |
other | AC * 24 |
ソースコード
#include <iostream>#include <algorithm>#include <string>#include <vector>#include <cmath>#include <map>#include <queue>#include <iomanip>#include <set>#include <tuple>#define mkp make_pair#define mkt make_tuple#define rep(i,n) for(int i = 0; i < (n); ++i)#define all(v) v.begin(),v.end()using namespace std;typedef long long ll;const ll MOD=1e9+7;template<class T> void chmin(T &a,const T &b){if(a>b) a=b;}template<class T> void chmax(T &a,const T &b){if(a<b) a=b;}const int L=6;const int MASK=(1<<6)-1;bool nthbit(int x,int n){if(x&(1<<n)) return true;return false;}int main(){cin.tie(0);ios::sync_with_stdio(false);ll N;int K;cin>>N>>K;vector<ll> A(K+2);rep(i,K) cin>>A[i+1];A[0]=1;A[K+1]=N;vector<int> trans((1<<L),0);for(int i=0;i<(1<<L);i++){int nxt=((i<<1)&MASK);if((nthbit(i,0)&nthbit(i,5))||(nthbit(i,1)&&nthbit(i,4))||(nthbit(i,2)&&nthbit(i,3))) nxt+=1;trans[i]=nxt;}vector<vector<int>> nxt((1<<L),vector<int> (61,0));rep(i,(1<<L)) nxt[i][0]=trans[i];for(ll k=1;k<=60;k++){for(int i=0;i<(1<<L);i++){nxt[i][k]=nxt[nxt[i][k-1]][k-1];}}int now=0;for(int i=K;i>=0;i--){ll d=A[i+1]-A[i];for(ll k=60;k>=0;k--){if((1ll<<k)&d) now=nxt[now][k];}if(i==0) break;now|=(1<<0);}if(now%2) cout<<"No"<<endl;else cout<<"Yes"<<endl;return 0;}