提出 #67716709

ソースコード 拡げる

#include <iostream>
#include <string>
using namespace std;

int pow2[19];
bool vis[1 << 18];
bool danger[1 << 18];
int q[1 << 18];

int main() {
    int t;
    cin >> t;
    pow2[0] = 1;
    for(int i = 1; i <= 18; i++) pow2[i] = pow2[i-1] * 2;
    while(t--) {
        int n;
        string s;
        cin >> n >> s;
        int total = pow2[n];
        for(int i = 1; i < total; i++) danger[i] = (s[i - 1] == '1');
        for(int i = 0; i < total; i++) vis[i] = 0;
        int front = 0, back = 0;
        for(int i = 0; i < n; i++) {
            int st = pow2[i];
            if(!danger[st]) {
                q[back++] = st;
                vis[st] = 1;
            }
        }
        while(front < back) {
            int cur = q[front++];
            for(int i = 0; i < n; i++) {
                if(!(cur & pow2[i])) {
                    int nxt = cur | pow2[i];
                    if(!danger[nxt] && !vis[nxt]) {
                        vis[nxt] = 1;
                        q[back++] = nxt;
                    }
                }
            }
        }
        if(vis[total - 1]) cout << "Yes\n";
        else cout << "No\n";
    }
    return 0;
}

提出情報

提出日時
問題 C - Mixture
ユーザ Naman____17
言語 C++ 17 (Clang 16.0.6)
得点 350
コード長 1208 Byte
結果 AC
実行時間 56 ms
メモリ 5228 KiB

ジャッジ結果

セット名 Sample All
得点 / 配点 0 / 0 350 / 350
結果
AC × 1
AC × 25
セット名 テストケース
Sample sample_01.txt
All sample_01.txt, test_01.txt, test_02.txt, test_03.txt, test_04.txt, test_05.txt, test_06.txt, test_07.txt, test_08.txt, test_09.txt, test_10.txt, test_11.txt, test_12.txt, test_13.txt, test_14.txt, test_15.txt, test_16.txt, test_17.txt, test_18.txt, test_19.txt, test_20.txt, test_21.txt, test_22.txt, test_23.txt, test_24.txt
ケース名 結果 実行時間 メモリ
sample_01.txt AC 1 ms 3644 KiB
test_01.txt AC 47 ms 3472 KiB
test_02.txt AC 48 ms 3484 KiB
test_03.txt AC 51 ms 3500 KiB
test_04.txt AC 50 ms 3520 KiB
test_05.txt AC 36 ms 4580 KiB
test_06.txt AC 32 ms 3476 KiB
test_07.txt AC 17 ms 4372 KiB
test_08.txt AC 44 ms 3524 KiB
test_09.txt AC 35 ms 5144 KiB
test_10.txt AC 43 ms 3448 KiB
test_11.txt AC 32 ms 5228 KiB
test_12.txt AC 33 ms 3516 KiB
test_13.txt AC 17 ms 4144 KiB
test_14.txt AC 18 ms 3576 KiB
test_15.txt AC 22 ms 4188 KiB
test_16.txt AC 25 ms 3584 KiB
test_17.txt AC 26 ms 4568 KiB
test_18.txt AC 29 ms 3556 KiB
test_19.txt AC 14 ms 4316 KiB
test_20.txt AC 56 ms 3524 KiB
test_21.txt AC 8 ms 4452 KiB
test_22.txt AC 54 ms 3380 KiB
test_23.txt AC 22 ms 5156 KiB
test_24.txt AC 38 ms 3556 KiB