結果
問題 | No.2283 Prohibit Three Consecutive |
ユーザー |
|
提出日時 | 2023-04-28 22:17:22 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 34 ms / 2,000 ms |
コード長 | 3,584 bytes |
コンパイル時間 | 898 ms |
コンパイル使用メモリ | 89,136 KB |
最終ジャッジ日時 | 2025-02-12 15:17:25 |
ジャッジサーバーID (参考情報) |
judge4 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 1 |
other | AC * 13 |
コンパイルメッセージ
main.cpp: In function ‘int main()’: main.cpp:75:18: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result] 75 | int tc; scanf("%d", &tc); while(tc) { tc--; | ~~~~~^~~~~~~~~~~ main.cpp:76:14: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result] 76 | scanf("%d %s", &n, ib); gn=n; | ~~~~~^~~~~~~~~~~~~~~~~
ソースコード
#include<stdio.h> #include<string.h> #include<stdlib.h> #include <map> #include <vector> #include <queue> #include <deque> #include <set> #include <stack> #include <algorithm> #include <array> #include <unordered_set> #include <unordered_map> #include <string> using namespace std; bool rcmp(int a, int b) { return a>b; } typedef long long LL; class mypcmp { public: bool operator()(const int& a, const int& b) { return a<b; } }; char ib[100004]; char dp[4][100004]; int gm, gn; char xk[4][4]; char nx[4][2]; char dfs(int m, int i) { if (i==gn) { return xk[m][gm]; } if (dp[m][i]!=-1) return dp[m][i]; char r=0, nm; if (ib[i]=='0') { nm = nx[m][0]; if (nm>=0) r=dfs(nm, i+1); } else if (ib[i]=='1') { nm = nx[m][1]; if (nm>=0) r=dfs(nm, i+1); } else { nm = nx[m][0]; if (nm>=0) r=dfs(nm, i+1); if (r==0) { nm = nx[m][1]; if (nm>=0) r=dfs(nm, i+1); } } dp[m][i]=r; return r; } int main() { int n, i, j; for (i=0; i<4; i++) for (j=0; j<4; j++) xk[i][j]=1; for (i=0; i<4; i++) nx[i][0]=nx[i][1]=-1; xk[0][0]=0; xk[0][1]=0; xk[1][3]=0; xk[2][0]=0; xk[3][2]=0; xk[3][3]=0; nx[0][1]=1; nx[1][0]=2; nx[1][1]=3; nx[2][0]=0; nx[2][1]=1; nx[3][0]=2; int tc; scanf("%d", &tc); while(tc) { tc--; scanf("%d %s", &n, ib); gn=n; if (ib[0]=='?'&&ib[1]=='?') { for (i=0; i<n; i++) for (j=0; j<4; j++) dp[j][i]=-1; gm=0; if (dfs(0, 2)) { printf("Yes\n"); continue; } for (i=0; i<n; i++) for (j=0; j<4; j++) dp[j][i]=-1; gm=1; if (dfs(1, 2)) { printf("Yes\n"); continue; } for (i=0; i<n; i++) for (j=0; j<4; j++) dp[j][i]=-1; gm=2; if (dfs(2, 2)) { printf("Yes\n"); continue; } for (i=0; i<n; i++) for (j=0; j<4; j++) dp[j][i]=-1; gm=3; if (dfs(3, 2)) { printf("Yes\n"); continue; } } else if (ib[0]=='?') { if (ib[1]=='0') { for (i=0; i<n; i++) for (j=0; j<4; j++) dp[j][i]=-1; gm=0; if (dfs(0, 2)) { printf("Yes\n"); continue; } for (i=0; i<n; i++) for (j=0; j<4; j++) dp[j][i]=-1; gm=2; if (dfs(2, 2)) { printf("Yes\n"); continue; } } else { for (i=0; i<n; i++) for (j=0; j<4; j++) dp[j][i]=-1; gm=1; if (dfs(1, 2)) { printf("Yes\n"); continue; } for (i=0; i<n; i++) for (j=0; j<4; j++) dp[j][i]=-1; gm=3; if (dfs(3, 2)) { printf("Yes\n"); continue; } } } else if (ib[1]=='?') { if (ib[0]=='0') { for (i=0; i<n; i++) for (j=0; j<4; j++) dp[j][i]=-1; gm=0; if (dfs(0, 2)) { printf("Yes\n"); continue; } for (i=0; i<n; i++) for (j=0; j<4; j++) dp[j][i]=-1; gm=1; if (dfs(1, 2)) { printf("Yes\n"); continue; } } else { for (i=0; i<n; i++) for (j=0; j<4; j++) dp[j][i]=-1; gm=2; if (dfs(2, 2)) { printf("Yes\n"); continue; } for (i=0; i<n; i++) for (j=0; j<4; j++) dp[j][i]=-1; gm=3; if (dfs(3, 2)) { printf("Yes\n"); continue; } } } else { for (i=0; i<n; i++) for (j=0; j<4; j++) dp[j][i]=-1; gm=0; if (ib[0]=='1') gm|=2; if (ib[1]=='1') gm|=1; if (dfs(gm, 2)) { printf("Yes\n"); continue; } } printf("No\n"); } return 0; }