結果

問題 No.3311 フィルター
コンテスト
ユーザー mono
提出日時 2025-10-24 21:33:56
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
TLE  
実行時間 -
コード長 2,056 bytes
コンパイル時間 2,114 ms
コンパイル使用メモリ 191,700 KB
実行使用メモリ 7,716 KB
最終ジャッジ日時 2025-10-24 21:34:03
合計ジャッジ時間 5,919 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 12 TLE * 1 -- * 7
権限があれば一括ダウンロードができます

ソースコード

diff # 

#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")
#include <bits/stdc++.h>
#include <stdlib.h>
using namespace std;
#define rep(i, a, n) for(ll i = a; i < n; i++)
#define rrep(i, a, n) for(ll i = a; i >= n; i--)
#define inr(l, x, r) (l <= x && x < r)
#define ll long long
#define ld long double
#define pii pair<int, int>
#define pll pair<ll, ll>
#define all(x) (x).begin(), (x).end()
//constexpr ll MOD = 1000000007;
constexpr ll MOD = 998244353;
constexpr int IINF = 1001001001;
constexpr ll INF = 1LL<<60;
template<class t,class u> void chmax(t&a,u b){if(a<b)a=b;}
template<class t,class u> void chmin(t&a,u b){if(b<a)a=b;}

ll gcd(ll a, ll b){
    if(a%b == 0){
      return b;
    }else{
      return gcd(b, a%b);
    }
}

ll lcm(ll a, ll b){
    return a*b / gcd(a, b);
}

ll powMod(ll x, ll n, ll mod) {
    if (n == 0) return 1 % mod;
    ll val = powMod(x, n / 2, mod);
    val *= val;
    val %= mod;
    if (n % 2 == 1) val *= x;
    return val % mod;
}

int main() {
    ll n, m; cin >> n >> m;
    vector<string> s(m);
    unordered_set<string> st;
    rep(i,0,m) cin >> s[i], st.insert(s[i]);
    rep(i,0,m){
        ll f = 0;
        rep(j,0,n){
            if(s[i][j] == '1') f = 1;
        }
        if(!f){
            cout << "No" << endl;
            return 0;
        }
    }
    string x(n,'0');
    rep(i,0,m)rep(j,i+1,m){
        rep(k,0,n){
            if(s[i][k] == '1' && s[j][k] == '1') x[k] = '1';
            else x[k] = '0';
        }
        if(st.find(x) == st.end()){
            cout << "No" << endl;
            return 0;
        }
    }
    auto dfs = [&](auto dfs, ll i, ll j)-> void {
        if(j == n){
            if(st.find(x) == st.end()){
                cout << "No" << endl;
                exit(0);
            }
            return;
        }else{
            x[j] = '1';
            dfs(dfs,i,j+1);
            if(s[i][j] == '0'){
                x[j] = '0';
                dfs(dfs,i,j+1);
            }
        }
    };
    rep(i,0,m) dfs(dfs,i,0);
    cout << "Yes" << endl;
    return 0;
}
0