結果
問題 |
No.2283 Prohibit Three Consecutive
|
ユーザー |
![]() |
提出日時 | 2023-04-28 21:33:49 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 8 ms / 2,000 ms |
コード長 | 1,358 bytes |
コンパイル時間 | 1,938 ms |
コンパイル使用メモリ | 192,772 KB |
最終ジャッジ日時 | 2025-02-12 14:55:11 |
ジャッジサーバーID (参考情報) |
judge3 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 1 |
other | AC * 13 |
ソースコード
#include<bits/stdc++.h> using namespace std; using ll = long long; int T, n; string s; int f[2][2], g[2][2]; bool ok(int a, int b){ for(int i=0; i<2; ++i){ for(int j=0; j<2; ++j) f[i][j] = g[i][j] = 0; } f[a][b] = 1; for(int i=2; i<n; ++i){ for(int j=0; j<2; ++j){ for(int k=0; k<2; ++k) g[j][k] = 0; } for(int j=0; j<2; ++j){ for(int k=0; k<2; ++k){ if(!f[j][k]) continue; for(int l=0; l<2; ++l){ if(j == k && j == l) continue; if(s[i] == '?' || s[i] == ('0' + l)){ g[k][l] = 1; } } } } for(int j=0; j<2; ++j){ for(int k=0; k<2; ++k){ f[j][k] = g[j][k]; } } } for(int i=0; i<2; ++i){ for(int j=0; j<2; ++j){ if(!f[i][j]) continue; if(i == j && i == a) continue; if(j == a && j == b) continue; return 1; } } return 0; } bool ok(){ for(int i=0; i<2; ++i){ if(s[0] != '?' && s[0] != ('0' + i)){ continue; } for(int j=0; j<2; ++j){ if(s[1] == '?' || s[1] == ('0' + j)){ if(ok(i, j)) return 1; } } } return 0; } int main(){ ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); cin >> T; while(T--){ cin >> n >> s; if(ok()){ cout << "Yes\n"; } else { cout << "No\n"; } } return 0; }