提出 #63545881

---

ソースコード 拡げる

#line 2 "Library/Template.hpp"

/**
 * @file Template.hpp
 * @author log K (lX57)
 * @brief Template - テンプレート
 * @version 1.9
 * @date 2024-10-27
 */

#line 2 "Library/Common.hpp"

/**
 * @file Common.hpp
 */

#include <algorithm>
#include <array>
#include <bitset>
#include <cassert>
#include <cstdint>
#include <deque>
#include <functional>
#include <iomanip>
#include <iostream>
#include <limits>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <tuple>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>
using namespace std;
#line 12 "Library/Template.hpp"
#define ALL(x) (x).begin(), (x).end()
#define RALL(x) (x).rbegin(), (x).rend()
#define SORT(x) sort(ALL(x))
#define RSORT(x) sort(RALL(x))
#define REVERSE(x) reverse(ALL(x))
#define SETPRE(digit) fixed << setprecision(digit)
#define POPCOUNT(x) __builtin_popcount(x)
#define SUM(x) reduce((x).begin(), (x).end())
#define CEIL(nume, deno) ((nume) + (deno) - 1) / (deno)
#define IOTA(x) iota((x).begin(), (x).end(), 0)
#define LOWERBOUND_IDX(arr, val) distance((arr).begin(), lower_bound((arr).begin(), (arr).end(), val))
#define UPPERBOUND_IDX(arr, val) distance((arr).begin(), upper_bound((arr).begin(), (arr).end(), val))

inline string Yn(bool flag){return (flag) ? "Yes" : "No";}
inline bool YnPrint(bool flag){cout << Yn(flag) << endl;return flag;}
inline string YN(bool flag){return (flag) ? "YES" : "NO";}
inline bool YNPrint(bool flag){cout << YN(flag) << endl;return flag;}
template<class T>
bool chmin(T &src, const T &cmp){if(src > cmp){src = cmp; return true;}return false;}
template<class T>
bool chmax(T &src, const T &cmp){if(src < cmp){src = cmp; return true;}return false;}
template<typename T>
inline bool between(T min, T x, T max){return min <= x && x <= max;}
template<typename T>
inline bool ingrid(T y, T x, T ymax, T xmax){return between(0, y, ymax - 1) && between(0, x, xmax - 1);}
template<typename T>
inline T median(T a, T b, T c){return between(b, a, c) || between(c, a, b) ? a : (between(a, b, c) || between(c, b, a) ? b : c);}
template<typename T>
inline T except(T src, T cond, T excp){return (src == cond ? excp : src);}
template<typename T>
inline T min(vector<T> &v){return *min_element((v).begin(), (v).end());}
template<typename T>
inline T max(vector<T> &v){return *max_element((v).begin(), (v).end());}
vector<int> make_sequence(int Size){
    vector<int> ret(Size);
    IOTA(ret);
    return ret;
}
template<typename T>
void make_unique(vector<T> &v){
    sort(v.begin(), v.end());
    auto itr = unique(v.begin(), v.end());
    v.erase(itr, v.end());
}

using ll = int64_t;
using ull = uint64_t;
using ld = long double;

const int INF_INT = numeric_limits<int>::max() >> 2;
const ll INF_LL = numeric_limits<ll>::max() >> 2;

using vi = vector<int>;
using vvi = vector<vi>;
using vl = vector<ll>;
using vvl = vector<vl>;
using pi = pair<int, int>;
using pl = pair<ll, ll>;
using vs = vector<string>;
template <typename T>
using pq = priority_queue<T>;
template <typename T>
using rpq = priority_queue<T, vector<T>, greater<T>>;

const int dx4[4] = {1, 0, -1, 0};
const int dy4[4] = {0, -1, 0, 1};
const int dx8[8] = {1, 1, 0, -1, -1, -1, 0, 1};
const int dy8[8] = {0, -1, -1, -1, 0, 1, 1, 1};

vector<pair<int, int>> adjacent(int current_y, int current_x, int max_y, int max_x, bool dir_8 = false){
    vector<pair<int, int>> ret;
    for(int d = 0; d < 4 * (1 + dir_8); ++d){
        int next_y = current_y + (dir_8 ? dy8[d] : dy4[d]);
        int next_x = current_x + (dir_8 ? dx8[d] : dx4[d]);
        if(0 <= next_y and next_y < max_y and 0 <= next_x and next_x < max_x){
            ret.emplace_back(next_y, next_x);
        }
    }
    return ret;
}

template <typename T1, typename T2>
ostream &operator<<(ostream &os, const pair<T1, T2> &p){
    os << p.first << ' ' << p.second;
    return os;
}

template <typename T1, typename T2>
istream &operator>>(istream &is, pair<T1, T2> &p){
    is >> p.first >> p.second;
    return is;
}

template <typename T>
istream &operator>>(istream &is, vector<T> &v){
    for (int i = 0; i < v.size(); ++i) is >> v[i];
    return is;
}

template <typename T>
ostream &operator<<(ostream &os, const vector<T> &v){
    os << v[0];
    for (int i = 1; i < v.size(); ++i){
        os << ' ' << v[i];
    }
    return os;
}

template <typename T>
ostream &operator<<(ostream &os, const vector<vector<T>> &v){
    os << v[0];
    for (int i = 0; i < v.size(); ++i){
        os << '\n' << v[i];
    }
    return os;
}

template<class T>
void Print(const T &a){
    cout << a << '\n';
}

template<class T, class... Ts>
void Print(const T &a, const Ts &...b){
    cout << a;
    (cout << ... << (cout << ' ', b));
    cout << '\n';
}

template<typename T1, typename T2>
vector<pair<T1, T2>> AssembleVectorPair(vector<T1> &v1, vector<T2> &v2){
    assert(v1.size() == v2.size());
    vector<pair<T1, T2>> v;
    for(int i = 0; i < v1.size(); ++i) v.push_back({v1[i], v2[i]});
    return v;
}

template<typename T1, typename T2>
pair<vector<T1>, vector<T2>> DisassembleVectorPair(vector<pair<T1, T2>> &v){
    vector<T1> v1;
    vector<T2> v2;
    transform(v.begin(), v.end(), back_inserter(v1), [](auto p){return p.first;});
    transform(v.begin(), v.end(), back_inserter(v2), [](auto p){return p.second;});
    return {v1, v2};
}

template<typename T1, typename T2, typename T3>
tuple<vector<T1>, vector<T2>, vector<T3>> DisassembleVectorTuple(vector<tuple<T1, T2, T3>> &v){
    vector<T1> v1;
    vector<T2> v2;
    vector<T3> v3;
    transform(v.begin(), v.end(), back_inserter(v1), [](auto p){return get<0>(p);});
    transform(v.begin(), v.end(), back_inserter(v2), [](auto p){return get<1>(p);});
    transform(v.begin(), v.end(), back_inserter(v3), [](auto p){return get<2>(p);});
    return {v1, v2, v3};
}

template<typename T1 = int, typename T2 = T1>
pair<vector<T1>, vector<T2>> InputVectorPair(int size){
    vector<pair<T1, T2>> v(size);
    for(auto &[p, q] : v) cin >> p >> q;
    return DisassembleVectorPair(v);
}

template<typename T1 = int, typename T2 = T1, typename T3 = T1>
tuple<vector<T1>, vector<T2>, vector<T3>> InputVectorTuple(int size){
    vector<tuple<T1, T2, T3>> v(size);
    for(auto &[p, q, r] : v) cin >> p >> q >> r;
    return DisassembleVectorTuple(v);
}

ll modpow(ll a, ll x, ll m){
    ll ret = 1, cur = a % m, rem = x;
    while(rem){
        if(rem & 1) ret = (ret * cur) % m;
        rem >>= 1, cur = (cur * cur) % m;
    }
    return ret;
}

#ifdef LOGK
#define VARIABLE(var) cerr << "# " << #var << " = " << var << endl;
#else
#define VARIABLE(...) 42
#endif
#line 2 "ABC396/G.cpp"

// ===================================================================
// 
// Main Program
// 
// Contest : ABC396
// Problem : G
// Date    : 2025-03-08 20:59:02
// 
// ===================================================================

void solve(){
    int H, W; cin >> H >> W;
    vector<string> A(H); cin >> A;

    auto FWHT = [&](vector<ll> &a, bool inv) -> void {
        int n = a.size();
        for(int k = 1; k < n; k <<= 1){
            for(int i = 0; i < n; i += k * 2){
                for(int j = 0; j < k; ++j){
                    ll u = a[i + j], v = a[i + j + k];
                    a[i + j] = u + v, a[i + j + k] = u - v;
                }
            }
        }
        if(inv){
            for(int i = 0; i < n; ++i) a[i] /= n;
        }
    };

    vector<ll> cnt(1 << W, 0);
    for(int i = 0; i < H; ++i){
        bitset<20> b(A[i]);
        ++cnt[b.to_ulong()];
    }
    vector<ll> B(1 << W, 0);
    for(int i = 0; i < 1 << W; ++i){
        B[i] = min(POPCOUNT(i), W - POPCOUNT(i));
    }
    auto f = cnt;
    auto g = B;
    FWHT(f, false), FWHT(g, false);
    for(int i = 0; i < 1 << W; ++i) f[i] *= g[i];
    FWHT(f, true);
    ll ans = INF_LL;
    for(int i = 0; i < 1 << W; ++i){
        chmin(ans, f[i]);
    }
    cout << ans << '\n';
}

int main(){
    cin.tie(0)->sync_with_stdio(false);
    // int T; cin >> T;
    // while(T--)
    solve();
}

提出情報

コンパイルエラー

Library/Template.hpp: In instantiation of ‘std::istream& operator>>(std::istream&, std::vector<_Tp>&) [with T = std::__cxx11::basic_string<char>; std::istream = std::basic_istream<char>]’:
ABC396/G.cpp:15:33:   required from here
Library/Template.hpp:107:23: warning: comparison of integer expressions of different signedness: ‘int’ and ‘std::vector<std::__cxx11::basic_string<char> >::size_type’ {aka ‘long unsigned int’} [-Wsign-compare]

ジャッジ結果