結果

問題 No.2283 Prohibit Three Consecutive
コンテスト
ユーザー shbgreenery
提出日時 2023-04-29 09:16:28
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 10 ms / 2,000 ms
コード長 2,092 bytes
コンパイル時間 1,629 ms
コンパイル使用メモリ 170,964 KB
実行使用メモリ 5,248 KB
最終ジャッジ日時 2024-11-18 08:04:24
合計ジャッジ時間 2,113 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other AC * 13
権限があれば一括ダウンロードができます

ソースコード

diff # 

// #include "atcoder/all"
#include <bits/stdc++.h>
using ll = long long;
const int MOD1000000007 = 1000000007;
const int MOD998244353 = 998244353;
const double PI = 3.14159265358979323846264338327950288;

void solve();

int main()
{
    std::ios_base::sync_with_stdio(false);
    // std::cin.tie(0);
#ifdef LOCAL
    freopen("input.txt", "r", stdin);
#endif
    // freopen("input.txt", "r", stdin);
    // freopen("output.txt", "w", stdout);
    int testcase;
    scanf("%d", &testcase);
    // std::cin >> testcase;
    while (testcase--)
        solve();
    return 0;
}
const int N = 1e5 + 5;
char ch[N];

bool check(std::string s)
{
    int cnt = 0;
    cnt |= 1 << (((s[0] - '0') * 2 + (s[1] - '0')));
    for (int j = 2; j < s.size(); j++)
    {
        int nxt = 0;
        for (int pre = 0; pre < 4; pre++)
        {
            if ((cnt >> pre) & 1)
            {
                int p1 = pre / 2;
                int p2 = pre % 2;
                if (s[j] == '0' || s[j] == '?')
                {
                    if (pre > 0)
                    {
                        nxt |= (1 << (p2 * 2));
                    }
                }
                if (s[j] == '1' || s[j] == '?')
                {
                    if (pre != 3)
                    {
                        nxt |= (1 << (p2 * 2 + 1));
                    }
                }
            }
        }
        cnt = nxt;
    }
    return cnt > 0;
}

void solve()
{
    int n;
    scanf("%d", &n);
    scanf("%s", ch);
    std::string s = ch;
    bool ok = false;
    if ((s[0] == '?' || s[0] == '0') && (s[1] == '?' || s[1] == '0'))
        ok |= check("00" + s.substr(2) + "00");
    if ((s[0] == '?' || s[0] == '0') && (s[1] == '?' || s[1] == '1'))
        ok |= check("01" + s.substr(2) + "01");
    if ((s[0] == '?' || s[0] == '1') && (s[1] == '?' || s[1] == '0'))
        ok |= check("10" + s.substr(2) + "10");
    if ((s[0] == '?' || s[0] == '1') && (s[1] == '?' || s[1] == '1'))
        ok |= check("11" + s.substr(2) + "11");
    if (ok)
        printf("Yes\n");
    else
        printf("No\n");
}
0