Submission #1275604

#	Time	Username	Problem	Language	Result	Execution time	Memory
1275604		tvgk	Council (JOI23_council)	C++20	62 / 100	319 ms	32452 KiB

council

#include<bits/stdc++.h>
using namespace std;
#define task "a"
#define ll long long
#define fi first
#define se second
#define ii pair<ll, ll>
const int mxN = 3e5 + 7;

int n, mask[mxN], m, dp[mxN][25], cnt[mxN], vote[mxN];

bool Check_bit(int u, int v)
{
    return (u >> v) & 1;
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie();
    cout.tie();
    //freopen(task".INP", "r", stdin);
    //freopen(task".OUT", "w", stdout);

    cin >> n >> m;
    for (int i = 1; i <= n; i++)
    {
        for (int j = 0; j < m; j++)
        {
            bool bit;
            cin >> bit;
            mask[i] += bit << j;
            vote[j] += bit;
        }
        cnt[mask[i]]++;
    }

    for (int i = 0; i < m; i++)
    {
        for (int j = 0; j < (1 << m); j++)
        {
            if (Check_bit(j, i))
                cnt[j ^ (1 << i)] += cnt[j];
        }
    }

    for (int i = 0; i < (1 << m); i++)
        dp[i][__builtin_popcount(i)] = cnt[i];

    for (int i = 0; i < m; i++)
    {
        for (int j = 0; j < (1 << m); j++)
        {
            if (Check_bit(j, i))
                continue;
            for (int num = 0; num < m; num++)
                dp[j ^ (1 << i)][num] += dp[j][num] - dp[j ^ (1 << i)][num + 1];
        }
    }

    for (int i = 1; i <= n; i++)
    {
        int ans = 0, ed = 0;
        for (int j = 0; j < m; j++)
        {
            if (vote[j] - Check_bit(mask[i], j) > n / 2)
                ans++;
            if (vote[j] - Check_bit(mask[i], j) == (n / 2))
                ed += (1 << j);
        }

        for (int j = 0; j <= m; j++)
        {
            if (dp[ed][j] - (__builtin_popcount(ed & mask[i]) == j))
            {
                ans += __builtin_popcount(ed) - j;
                break;
            }
        }
        cout << ans << '\n';
    }
}

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