結果
問題 | No.1267 Stop and Coin Game |
ユーザー |
![]() |
提出日時 | 2020-10-23 22:29:02 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 92 ms / 2,000 ms |
コード長 | 2,970 bytes |
コンパイル時間 | 2,655 ms |
コンパイル使用メモリ | 210,680 KB |
最終ジャッジ日時 | 2025-01-15 13:27:04 |
ジャッジサーバーID (参考情報) |
judge5 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 4 |
other | AC * 43 |
ソースコード
#pragma GCC optimize ("Ofast")#include<bits/stdc++.h>using namespace std;inline int my_getchar_unlocked(){static char buf[1048576];static int s = 1048576;static int e = 1048576;if(s == e && e == 1048576){e = fread_unlocked(buf, 1, 1048576, stdin);s = 0;}if(s == e){return EOF;}return buf[s++];}inline void rd(int &x){int k;int m=0;x=0;for(;;){k = my_getchar_unlocked();if(k=='-'){m=1;break;}if('0'<=k&&k<='9'){x=k-'0';break;}}for(;;){k = my_getchar_unlocked();if(k<'0'||k>'9'){break;}x=x*10+k-'0';}if(m){x=-x;}}inline void rd(long long &x){int k;int m=0;x=0;for(;;){k = my_getchar_unlocked();if(k=='-'){m=1;break;}if('0'<=k&&k<='9'){x=k-'0';break;}}for(;;){k = my_getchar_unlocked();if(k<'0'||k>'9'){break;}x=x*10+k-'0';}if(m){x=-x;}}struct MY_WRITER{char buf[1048576];int s;int e;MY_WRITER(){s = 0;e = 1048576;}~MY_WRITER(){if(s){fwrite_unlocked(buf, 1, s, stdout);}}};MY_WRITER MY_WRITER_VAR;void my_putchar_unlocked(int a){if(MY_WRITER_VAR.s == MY_WRITER_VAR.e){fwrite_unlocked(MY_WRITER_VAR.buf, 1, MY_WRITER_VAR.s, stdout);MY_WRITER_VAR.s = 0;}MY_WRITER_VAR.buf[MY_WRITER_VAR.s++] = a;}inline void wt_L(char a){my_putchar_unlocked(a);}inline void wt_L(const char c[]){int i=0;for(i=0;c[i]!='\0';i++){my_putchar_unlocked(c[i]);}}int N;long long V;long long A[20];int ok[1200000];int dp[1200000];int main(){int mask;long long s;rd(N);rd(V);{int Lj4PdHRW;for(Lj4PdHRW=(0);Lj4PdHRW<(N);Lj4PdHRW++){rd(A[Lj4PdHRW]);}}for(mask=(0);mask<(1<<N);mask++){int i;s = 0;for(i=(0);i<(N);i++){if(((mask) &(1<<(i)))){s += A[i];}}if(s <= V){ok[mask] = 1;}}if(ok[(1<<N)-1]){wt_L("Draw");wt_L('\n');return 0;}for(mask=(1<<N)-1;mask>=(0);mask--){int i;if(!ok[mask]){dp[mask] = 1;continue;}for(i=(0);i<(N);i++){if(!((mask) &(1<<(i)))&& dp[mask ^ (1<<i)] == 0){dp[mask] = 1;break;}}}if(dp[0]){wt_L("First");wt_L('\n');}else{wt_L("Second");wt_L('\n');}return 0;}// cLay varsion 20201018-2// --- original code ---// int N; ll V, A[20];// int ok[12d5], dp[12d5];// {// ll s;// rd(N,V,A(N));// rep(mask,1<<N){// s = 0;// rep(i,N) if(BIT_ith(mask, i)) s += A[i];// if(s <= V) ok[mask] = 1;// }// if(ok[(1<<N)-1]) wt("Draw"), return 0;//// rrep(mask,1<<N){// if(!ok[mask]) dp[mask] = 1, continue;// rep(i,N) if(!BIT_ith(mask,i) && dp[mask ^ (1<<i)] == 0) dp[mask] = 1, break;// }//// wt(if[dp[0], "First", "Second"]);// }