結果

問題 No.2283 Prohibit Three Consecutive
コンテスト
ユーザー siman
提出日時 2023-05-01 15:32:47
言語 C++17(clang)
(17.0.6 + boost 1.87.0)
結果
AC  
実行時間 41 ms / 2,000 ms
コード長 2,207 bytes
コンパイル時間 2,281 ms
コンパイル使用メモリ 141,544 KB
実行使用メモリ 6,820 KB
最終ジャッジ日時 2024-11-20 14:41:06
合計ジャッジ時間 2,806 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other AC * 13
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <cassert>
#include <cmath>
#include <algorithm>
#include <iostream>
#include <iomanip>
#include <climits>
#include <map>
#include <queue>
#include <set>
#include <cstring>
#include <vector>

using namespace std;
typedef long long ll;

bool solver(int f, int N, string S) {
  if (f >> 1 & 1) {
    S[0] = '1';
    S.append("1");
  } else {
    S[0] = '0';
    S.append("0");
  }
  if (f >> 0 & 1) {
    S[1] = '1';
    S.append("1");
  } else {
    S[1] = '0';
    S.append("0");
  }

  bool is_valid[N + 2][4];
  memset(is_valid, false, sizeof(is_valid));

  is_valid[1][f] = true;

  for (int i = 2; i < N + 2; ++i) {
    for (int mask = 0; mask < 4; ++mask) {
      if (not is_valid[i - 1][mask]) continue;

      switch(mask) {
        case 0:
          if (S[i] == '1' || S[i] == '?') {
            is_valid[i][1] = true;
          }
          break;
        case 1:
          if (S[i] == '0' || S[i] == '?') {
            is_valid[i][2] = true;
          }
          if (S[i] == '1' || S[i] == '?') {
            is_valid[i][3] = true;
          }
          break;
        case 2:
          if (S[i] == '0' || S[i] == '?') {
            is_valid[i][0] = true;
          }
          if (S[i] == '1' || S[i] == '?') {
            is_valid[i][1] = true;
          }
          break;
        case 3:
          if (S[i] == '0' || S[i] == '?') {
            is_valid[i][2] = true;
          }
          break;
      }
    }

    bool valid = false;
    for (int mask = 0; mask < 4; ++mask) {
      valid |= is_valid[i][mask];
    }
    if (not valid) {
      return false;
    }
  }

  return true;
}

int main() {
  int T;
  cin >> T;

  for (int t = 0; t < T; ++t) {
    int N;
    string S;

    cin >> N;
    cin >> S;

    bool res = false;

    for (int mask = 0; mask < 4; ++mask) {
      bool ok = true;

      for (int i = 0; i < 2; ++i ){
        if (mask >> i & 1) {
          ok &= (S[1 - i] == '1' || S[1 - i] == '?');
        } else { 
          ok &= (S[1 - i] == '0' || S[1 - i] == '?');
        }
      }

      if (ok) {
        res |= solver(mask, N, S);
      }
    }

    if (res) {
      cout << "Yes" << endl;
    } else {
      cout << "No" << endl;
    }
  }

  return 0;
}
0