Submission #1258309

#	Time	Username	Problem	Language	Result	Execution time	Memory
1258309		NHristov	Council (JOI23_council)	C++20	100 / 100	483 ms	24612 KiB

council

#include <bits/stdc++.h>
#define endl '\n'

using namespace std;

const int N = 3e5 + 5;
const int M = 20;

int n, m;

struct Save
{
    int mx1, pos1;
    int mx2, pos2;
};

bool vote[N][M];
int cnt[M];

bool f[(1 << M)];
Save dp[(1 << M)];

constexpr Save upd(const Save &a, const Save &b)
{
    Save ret{0, 0, 0, 0};

    ret.mx1 = max(a.mx1, b.mx1);

    if (ret.mx1 == a.mx1)
    {
        ret.pos1 = a.pos1;
    }
    else
    {
        ret.pos1 = b.pos1;
    }

    if (a.mx1 > ret.mx2 && a.pos1 != ret.pos1)
    {
        ret.mx2 = a.mx1;
        ret.pos2 = a.pos1;
    }

    if (b.mx1 > ret.mx2 && b.pos1 != ret.pos1)
    {
        ret.mx2 = b.mx1;
        ret.pos2 = b.pos1;
    }

    if (a.mx2 > ret.mx2 && a.pos2 != ret.pos1)
    {
        ret.mx2 = a.mx2;
        ret.pos2 = a.pos2;
    }

    if (b.mx2 > ret.mx2 && b.pos2 != ret.pos1)
    {
        ret.mx2 = b.mx2;
        ret.pos2 = b.pos2;
    }

    return ret;
}

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);

    cin >> n >> m;

    for (int i = 0; i < n; i++)
    {
        int mask = 0;

        for (int q = 0; q < m; q++)
        {
            cin >> vote[i][q];

            if (!vote[i][q])
            {
                mask += (1 << q);
            }
            else
            {
                cnt[q]++;
            }
        }

        f[mask] = 1;
        dp[mask] = upd(dp[mask], Save{__builtin_popcount(mask), i, 0, 0});
    }

    for (int mask = (1 << m) - 1; mask >= 0; mask--)
    {
        if (f[mask])
        {
            for (int i = 0; i < m; i++)
            {
                if (mask & (1 << i))
                {
                    if (dp[mask].mx2 == dp[mask].mx1)
                    {
                        dp[mask ^ (1 << i)] = upd(dp[mask ^ (1 << i)], Save{__builtin_popcount(mask ^ (1 << i)), dp[mask].pos1, __builtin_popcount(mask ^ (1 << i)), dp[mask].pos2});
                    }
                    else
                    {
                        dp[mask ^ (1 << i)] = upd(dp[mask ^ (1 << i)], Save{__builtin_popcount(mask ^ (1 << i)), dp[mask].pos1, 0, 0});
                    }

                    f[mask ^ (1 << i)] = 1;
                }
            }
        }
    }

    for (int i = 0; i < m; i++)
    {
        for (int mask = (1 << i); mask < (1 << m); mask = (mask + 1) | (1 << i))
        {
            dp[mask] = upd(dp[mask], dp[mask ^ (1 << i)]);
        }
    }

    for (int i = 0; i < n; i++)
    {
        int good = 0, mask = 0;

        for (int q = 0; q < m; q++)
        {
            int rem = cnt[q] - vote[i][q];

            if (rem > n / 2)
            {
                good++;
            }

            if (rem == n / 2)
            {
                mask |= (1 << q);
            }
        }

        int ans = good;

        if (dp[mask].pos1 == i)
        {
            ans += dp[mask].mx2;
        }
        else
        {
            ans += dp[mask].mx1;
        }

        cout << ans << endl;
    }

    return 0;
}

• 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