Submission #979018

#	Time	Username	Problem	Language	Result	Execution time	Memory
979018		abc864197532	Council (JOI23_council)	C++17	100 / 100	554 ms	38808 KiB

council

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pb push_back
#define all(x) x.begin(), x.end()
#define pii pair<int, int>
const int N = 300003, mod = 998244353;

int a[N], sum[20];

int main() {
    ios::sync_with_stdio(false), cin.tie(0);
    int n, m;
    cin >> n >> m;
    for (int i = 0; i < n; ++i) {
        for (int j = 0, x; j < m; ++j) {
            cin >> x;
            sum[j] += x;
            if (x) a[i] |= 1 << j;
        }
    }
    int res = 0;
    vector <int> b, c;
    for (int k = 0; k < m; ++k) {
        if (sum[k] == n / 2 + 1) {
            b.pb(1), c.pb(k);
        } else if (sum[k] == n / 2) {
            b.pb(2), c.pb(k);
        } else if (sum[k] >= n / 2) {
            res++;
        }
    }
    for (int i = 0; i < n; ++i) {
        int now = 0;
        for (int j = 0; j < c.size(); ++j) {
            if (~a[i] >> c[j] & 1) {
                now |= 1 << j;
            }
        }
        a[i] = now;
    }
    m = c.size();
    vector <array <int, 2>> dp(1 << m, {-1, -1});
    auto upd = [&](int s, int pos) {
        if (pos == dp[s][0] || pos == dp[s][1]) {
            return;
        }
        if (dp[s][0] == -1) {
            dp[s][0] = pos;
        } else if (dp[s][1] == -1) {
            dp[s][1] = pos;
        }
    };
    for (int i = 0; i < n; ++i) {
        upd(a[i], i);
    }
    for (int j = 0; j < m; ++j) {
        for (int s = 0; s < 1 << m; ++s) if (~s >> j & 1) {
            for (int i : {0, 1}) if (dp[s ^ (1 << j)][i] != -1) {
                upd(s, dp[s ^ (1 << j)][i]);
            }
        }
    }
    vector <pii> mx(1 << m, {0, -1}), smx(1 << m, {0, -1});
    for (int s = 0; s < 1 << m; ++s) {
        if (dp[s][0] != -1) {
            mx[s] = {__builtin_popcount(s), dp[s][0]};
        }
        if (dp[s][1] != -1) {
            smx[s] = {__builtin_popcount(s), dp[s][1]};
        }
    }
    auto upd2 = [&](int s, pii v) {
        if (mx[s].second == v.second) {
            mx[s] = max(mx[s], v);
        } else if (smx[s].second == v.second) {
            smx[s] = max(smx[s], v);
        } else {
            if (mx[s] < v) {
                smx[s] = mx[s], mx[s] = v;
            } else if (smx[s] < v) {
                smx[s] = v;
            }
        }
        if (mx[s] < smx[s]) {
            swap(mx[s], smx[s]);
        }
    };
    for (int s = 1; s < 1 << m; ++s) {
        for (int i = 0; i < m; ++i) if (s >> i & 1) {
            upd2(s, mx[s ^ (1 << i)]);
            upd2(s, smx[s ^ (1 << i)]);
        }
    }
    for (int i = 0; i < n; ++i) {
        int msk = 0;
        int cur = 0;
        for (int j = 0; j < m; ++j) {
            if (b[j] == 1) {
                if (a[i] >> j & 1) {
                    cur++;
                } else {
                    msk |= 1 << j;
                }
            } else {
                if (a[i] >> j & 1) {
                    msk |= 1 << j;
                }
            }
        }
        int ans;
        if (mx[msk].second == i) {
            ans = smx[msk].first;
        } else {
            ans = mx[msk].first;
        }
        int tans = 0;
        for (int j = 0; j < n; ++j) if (i ^ j) {
            tans = max(tans, __builtin_popcount(msk & a[j]));
        }
        cout << res + cur + ans << '\n';
    }
}

Compilation message (stderr)

council.cpp: In function 'int main()':
council.cpp:35:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   35 |         for (int j = 0; j < c.size(); ++j) {
      |                         ~~^~~~~~~~~~

• Subtask 1: 8 / 8
• Subtask 2: 8 / 8
• Subtask 3: 6 / 6
• Subtask 4: 19 / 19
• Subtask 5: 15 / 15
• Subtask 6: 22 / 22
• Subtask 7: 22 / 22