#842817 (C++17) No.2270 T0空間

提出ソース

結果

問題	No.2270 T0空間
ユーザー	遭難者
提出日時	2023-02-24 16:30:35
言語	C++17 (gcc 12.3.0 + boost 1.83.0)
結果	AC
実行時間	245 ms / 2,000 ms
コード長	9,344 bytes
コンパイル時間	4,707 ms
コンパイル使用メモリ	271,488 KB
実行使用メモリ	6,944 KB
最終ジャッジ日時	2024-09-13 01:32:20
合計ジャッジ時間	9,503 ms
ジャッジサーバーID （参考情報）	judge3 / judge2

このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	2 ms 6,812 KB
testcase_01	AC	2 ms 6,816 KB
testcase_02	AC	2 ms 6,940 KB
testcase_03	AC	2 ms 6,944 KB
testcase_04	AC	1 ms 6,944 KB
testcase_05	AC	2 ms 6,944 KB
testcase_06	AC	3 ms 6,944 KB
testcase_07	AC	1 ms 6,940 KB
testcase_08	AC	2 ms 6,940 KB
testcase_09	AC	2 ms 6,944 KB
testcase_10	AC	2 ms 6,944 KB
testcase_11	AC	33 ms 6,944 KB
testcase_12	AC	28 ms 6,944 KB
testcase_13	AC	53 ms 6,940 KB
testcase_14	AC	65 ms 6,944 KB
testcase_15	AC	48 ms 6,940 KB
testcase_16	AC	78 ms 6,944 KB
testcase_17	AC	245 ms 6,940 KB
testcase_18	AC	159 ms 6,944 KB
testcase_19	AC	156 ms 6,940 KB
testcase_20	AC	155 ms 6,940 KB
testcase_21	AC	62 ms 6,944 KB

権限があれば一括ダウンロードができます

ソースコード

raw source code

#include <bits/stdc++.h>
#include <atcoder/all>
using namespace std;
using ll = long long;
using ld = long double;
using ull = unsigned long long;
using uint = unsigned;
using vi = vector<int>;
using vvi = vector<vi>;
using vll = vector<ll>;
using vcll = vector<vll>;
using pii = pair<int, int>;
using vpii = vector<pii>;
using pll = pair<ll, ll>;
using pdd = pair<ld, ld>;
using tuplis = array<ll, 3>;
template <class T>
using pq = priority_queue<T, vector<T>, greater<T>>;
const ll LINF = 0x1fffffffffffffff;
const ll MINF = 0x7fffffffffff;
const int INF = 0x3fffffff;
const int MOD = 1000000007;
const int MODD = 998244353;
const ld DINF = numeric_limits<ld>::infinity();
const ld EPS = 1e-9;
const ld PI = 3.1415926535897932;
const ll dx[] = {0, 1, 0, -1, 1, -1, 1, -1};
const ll dy[] = {1, 0, -1, 0, 1, 1, -1, -1};
#define overload5(a, b, c, d, e, name, ...) name
#define overload4(a, b, c, d, name, ...) name
#define overload3(a, b, c, name, ...) name
#define rep1(n) for (ll i = 0; i < n; ++i)
#define rep2(i, n) for (ll i = 0; i < n; ++i)
#define rep3(i, a, b) for (ll i = a; i < b; ++i)
#define rep4(i, a, b, c) for (ll i = a; i < b; i += c)
#define rep(...) overload4(__VA_ARGS__, rep4, rep3, rep2, rep1)(__VA_ARGS__)
#define rrep1(n) for (ll i = n; i--;)
#define rrep2(i, n) for (ll i = n; i--;)
#define rrep3(i, a, b) for (ll i = b; i-- > (a);)
#define rrep4(i, a, b, c) for (ll i = (a) + ((b) - (a)-1) / (c) * (c); i >= (a); i -= c)
#define rrep(...) overload4(__VA_ARGS__, rrep4, rrep3, rrep2, rrep1)(__VA_ARGS__)
#define each1(i, a) for (auto &&i : a)
#define each2(x, y, a) for (auto &&[x, y] : a)
#define each3(x, y, z, a) for (auto &&[x, y, z] : a)
#define each4(w, x, y, z, a) for (auto &&[w, x, y, z] : a)
#define each(...) overload5(__VA_ARGS__, each4, each3, each2, each1)(__VA_ARGS__)
#define all1(i) begin(i), end(i)
#define all2(i, a) begin(i), begin(i) + a
#define all3(i, a, b) begin(i) + a, begin(i) + b
#define all(...) overload3(__VA_ARGS__, all3, all2, all1)(__VA_ARGS__)
#define rall1(i) rbegin(i), rend(i)
#define rall2(i, a) rbegin(i), rbegin(i) + a
#define rall3(i, a, b) rbegin(i) + a, rbegin(i) + b
#define rall(...) overload3(__VA_ARGS__, rall3, rall2, rall1)(__VA_ARGS__)
#define sum(...) accumulate(all(__VA_ARGS__), 0LL)
#define dsum(...) accumulate(all(__VA_ARGS__), 0.0L)
#define Msum(...) accumulate(all(__VA_ARGS__), Modint{})
#define elif else if
#define INT(...)     \
    int __VA_ARGS__; \
    in(__VA_ARGS__)
#define LL(...)     \
    ll __VA_ARGS__; \
    in(__VA_ARGS__)
#define ULL(...)     \
    ull __VA_ARGS__; \
    in(__VA_ARGS__)
#define STR(...)        \
    string __VA_ARGS__; \
    in(__VA_ARGS__)
#define CHR(...)      \
    char __VA_ARGS__; \
    in(__VA_ARGS__)
#define DBL(...)        \
    double __VA_ARGS__; \
    in(__VA_ARGS__)
#define LD(...)     \
    ld __VA_ARGS__; \
    in(__VA_ARGS__)
#define vec(type, name, ...) vector<type> name(__VA_ARGS__)
#define VEC(type, name, size) \
    vector<type> name(size);  \
    in(name)
#define vv(type, name, h, ...) vector name(h, vector<type>(__VA_ARGS__))
#define VV(type, name, h, w)         \
    vector name(h, vector<type>(w)); \
    in(name)
#define vvv(type, name, h, w, ...) vector name(h, vector(w, vector<type>(__VA_ARGS__)))
template <class T>
auto min(const T &a)
{
    return *min_element(all(a));
}
template <class T>
auto max(const T &a) { return *max_element(all(a)); }
template <class T, class U>
ll count(const T &a, const U &b) { return count(all(a), b); }
template <class T, class F>
ll count_if(const T &a, F b) { return count_if(all(a), b); }
template <class T, class F>
void filter(T &a, F b) { a.erase(remove_if(all(a), not_fn(b)), a.end()); }
template <class T, class F = less<>>
void sor(T &a, F b = F{}) { sort(all(a), b); }
template <class T>
void rev(T &a) { reverse(all(a)); }
template <class T>
void uniq(T &a)
{
    sor(a);
    a.erase(unique(all(a)), end(a));
}
ll popcnt(ull a) { return __builtin_popcountll(a); }
ll intpow(ll a, ll b)
{
    ll ans = 1;
    while (b)
    {
        if (b & 1)
            ans *= a;
        a *= a;
        b /= 2;
    }
    return ans;
}
ll modpow(ll a, ll b, ll p)
{
    ll ans = 1;
    while (b)
    {
        if (b & 1)
            (ans *= a) %= p;
        (a *= a) %= p;
        b /= 2;
    }
    return ans;
}
template <class T>
bool chmin(T &a, const T &b)
{
    if (a <= b)
        return 0;
    a = b;
    return 1;
}
template <class T>
bool chmax(T &a, const T &b)
{
    if (a >= b)
        return 0;
    a = b;
    return 1;
}
template <class T, class U>
bool chmin(T &a, const U &b) { return chmin(a, (T)b); }
template <class T, class U>
bool chmax(T &a, const U &b) { return chmax(a, (T)b); }
vector<ll> iota(ll n, ll begin = 0)
{
    vector<ll> a(n);
    iota(a.begin(), a.end(), begin);
    return a;
}
vector<pll> factor(ull x)
{
    vector<pll> ans;
    for (ull i = 2; i * i <= x; i++)
        if (x % i == 0)
        {
            ans.push_back({i, 1});
            while ((x /= i) % i == 0)
                ans.back().second++;
        }
    if (x != 1)
        ans.push_back({x, 1});
    return ans;
}
template <class T>
unordered_map<T, ll> press(vector<T> a)
{
    uniq(a);
    unordered_map<T, ll> ans;
    rep(a.size()) ans[a[i]] = i;
    return ans;
}
template <class T>
auto run_press(const T &a)
{
    vector<pair<decay_t<decltype(a[0])>, ll>> ans;
    each(x, a)
    {
        if (ans.empty() || ans.back().first != x)
            ans.emplace_back(x, 1);
        else
            ans.back().second++;
    }
    return ans;
}
template <class... Ts>
void in(Ts &...t);
[[maybe_unused]] void print() {}
template <class T, class... Ts>
void print(const T &t, const Ts &...ts);
template <class... Ts>
void out(const Ts &...ts)
{
    print(ts...);
    cout << '\n';
}
namespace IO
{
#define VOID(a) decltype(void(a))
    struct S
    {
        S()
        {
            cin.tie(nullptr)->sync_with_stdio(0);
            fixed(cout).precision(12);
        }
    } S;
    template <int I>
    struct P : P<I - 1>
    {
    };
    template <>
    struct P<0>
    {
    };
    template <class T>
    void i(T &t) { i(t, P<3>{}); }
    void i(vector<bool>::reference t, P<3>)
    {
        int a;
        i(a);
        t = a;
    }
    template <class T>
    auto i(T &t, P<2>) -> VOID(cin >> t) { cin >> t; }
    template <class T>
    auto i(T &t, P<1>) -> VOID(begin(t))
    {
        for (auto &&x : t)
            i(x);
    }
    template <class T, size_t... idx>
    void ituple(T &t, index_sequence<idx...>) { in(get<idx>(t)...); }
    template <class T>
    auto i(T &t, P<0>) -> VOID(tuple_size<T>{}) { ituple(t, make_index_sequence<tuple_size<T>::value>{}); }
    template <class T>
    void o(const T &t) { o(t, P<4>{}); }
    template <size_t N>
    void o(const char (&t)[N], P<4>) { cout << t; }
    template <class T, size_t N>
    void o(const T (&t)[N], P<3>)
    {
        o(t[0]);
        for (size_t i = 1; i < N; i++)
        {
            o(' ');
            o(t[i]);
        }
    }
    template <class T>
    auto o(const T &t, P<2>) -> VOID(cout << t) { cout << t; }
    template <class T>
    auto o(const T &t, P<1>) -> VOID(begin(t))
    {
        bool first = 1;
        for (auto &&x : t)
        {
            if (first)
                first = 0;
            else
                o(' ');
            o(x);
        }
    }
    template <class T, size_t... idx>
    void otuple(const T &t, index_sequence<idx...>) { print(get<idx>(t)...); }
    template <class T>
    auto o(T &t, P<0>) -> VOID(tuple_size<T>{}) { otuple(t, make_index_sequence<tuple_size<T>::value>{}); }
#undef VOID
}
#define unpack(a)               \
    (void)initializer_list<int> \
    {                           \
        (a, 0)...               \
    }
template <class... Ts>
void in(Ts &...t)
{
    unpack(IO::i(t));
}
template <class T, class... Ts>
void print(const T &t, const Ts &...ts)
{
    IO::o(t);
    unpack(IO::o((cout << ' ', ts)));
}
#undef unpack
#ifdef DEBUG
ll __lg(ull x)
{
    return 63 - __builtin_clzll(x);
}
#define debug(...)           \
    {                        \
        print(#__VA_ARGS__); \
        print(":");          \
        out(__VA_ARGS__);    \
    }
#else
#define debug(...) void(0)
#endif
#define YESNO(yes, no)       \
    void yes(bool i = 1)     \
    {                        \
        out(i ? #yes : #no); \
    }                        \
    void no()                \
    {                        \
        out(#no);            \
    }
YESNO(first, second)
YESNO(First, Second)
YESNO(Yes, No)
YESNO(YES, NO)
YESNO(possible, impossible)
YESNO(POSSIBLE, IMPOSSIBLE)
void Case(ll i)
{
    print("Case #");
    print(i);
    print(": ");
}
using namespace atcoder;
using namespace IO;
constexpr int N = 1 << 8;
void solve()
{
    INT(n, m);
    vector<bitset<N>> a(m);
    rep(i, m)
    {
        STR(s);
        a[i] = bitset<N>(s);
    }
    bitset<N> nn;
    rep(i, n) nn[i] = true;
    rep(i, n)
    {
        bitset<N> t1, t2;
        for (auto &ss : a)
        {
            if (ss[i])
                t2 |= ~ss;
            else
                t1 |= ss;
        }
        t1 |= t2;
        t1 &= nn;
        t1[i] = true;
        if (t1 != nn)
        {
            out("No");
            return;
        }
    }
    out("Yes");
    return;
}
int main()
{
    solve();
    return 0;
}

yukicoder

結果

テストケース

ソースコード