Submission #768886

#	Time	Username	Problem	Language	Result	Execution time	Memory
768886		danikoynov	Council (JOI23_council)	C++14	100 / 100	750 ms	365840 KiB

council

/**
 ____ ____ ____ ____ ____ ____
||l |||e |||i |||n |||a |||d ||
||__|||__|||__|||__|||__|||__||
|/__\|/__\|/__\|/__\|/__\|/__\|

**/

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

using namespace std;
typedef long long ll;

void speed()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
}

const int maxn = 3e5 + 10, maxm = 21;
int n, m, imp[maxm], cnt[maxm];
bool a[maxn][maxm];
pair < int, int > dp[maxm][(1 << maxm)][2];
int val_mask[maxn], rev_mask[maxn];
void solve()
{

    cin >> n >> m;
    for (int i = 1; i <= n; i ++)
        for (int j = 0; j < m; j ++)
            cin >> a[i][j], cnt[j] += a[i][j];

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

    for (int i = 1; i <= n; i ++)
    {
        for (int j = 0; j < m; j ++)
        {
            val_mask[i] = (val_mask[i] + (1 << j) * a[i][j]);
            rev_mask[i] = (rev_mask[i] + (1 << j) * (1 - a[i][j]));

            ///cout << "mask " << rev_mask[i] << endl;

        }
        int mask = rev_mask[i];

        int val = __builtin_popcount(mask);
        if (dp[0][mask][0].second == i)
        {
            dp[0][mask][0].first = max(dp[0][mask][0].first, val);
        }
        else if (dp[0][mask][1].second == i)
        {
            dp[0][mask][1].first = max(dp[0][mask][1].first, val);
            if (dp[0][mask][0].first < dp[0][mask][1].first)
                swap(dp[0][mask][0], dp[0][mask][1]);
        }
        else if (val > dp[0][mask][0].first)
        {
            dp[0][mask][1] = dp[0][mask][0];
            dp[0][mask][0] = {val, i};
        }
        else if (val > dp[0][mask][1].first)
        {
            dp[0][mask][1] = {val, i};
        }

    }

    for (int mask = (1 << m) - 1; mask >= 0; mask --)
    {
        for (int bit = 0; bit < m; bit ++)
        {
            if ((mask & (1 << bit)) > 0)
                continue;
            int new_mask = (mask ^ (1 << bit));
            int val = dp[0][new_mask][0].first - 1, idx = dp[0][new_mask][0].second;
            if (dp[0][mask][0].second == idx)
            {
                if (val > dp[0][mask][0].first)
                    dp[0][mask][0].first = val;
            }
            else if (dp[0][mask][1].second == idx)
            {
                if (val > dp[0][mask][1].first)
                    dp[0][mask][1].first = val;
                if (dp[0][mask][0].first < dp[0][mask][1].first)
                    swap(dp[0][mask][0], dp[0][mask][1]);
            }
            else if (val > dp[0][mask][0].first)
            {
                dp[0][mask][1] = dp[0][mask][0];
                dp[0][mask][0] = {val, idx};
            }
            else if (val > dp[0][mask][1].first)
            {
                dp[0][mask][1] = {val, idx};
            }

            val = dp[0][new_mask][1].first - 1;
            idx = dp[0][new_mask][1].second;
            if (dp[0][mask][0].second == idx)
            {
                if (val > dp[0][mask][0].first)
                    dp[0][mask][0].first = val;
            }
            else if (dp[0][mask][1].second == idx)
            {
                if (val > dp[0][mask][1].first)
                    dp[0][mask][1].first = val;
                if (dp[0][mask][0].first < dp[0][mask][1].first)
                    swap(dp[0][mask][0], dp[0][mask][1]);
            }
            else if (val > dp[0][mask][0].first)
            {
                dp[0][mask][1] = dp[0][mask][0];
                dp[0][mask][0] = {val, idx};
            }
            else if (val > dp[0][mask][1].first)
            {
                dp[0][mask][1] = {val, idx};
            }
        }
    }
    /**int val = __builtin_popcount(rev_mask[i]);
    if (dp[0][rev_mask[i]][0].second == i)
    {
        dp[0][rev_mask[i]][0].first = max(dp[0][rev_mask[i]][0].first, val);
    }
    else if (dp[0][rev_mask[i]][1].second == i)
    {
        dp[0][rev_mask[i]][1].first = max(dp[0][rev_mask[i]][1].first, val);
        if (dp[0][rev_mask[i]][0].first < dp[0][rev_mask[i]][1].first)
            swap(dp[0][rev_mask[i]][0], dp[0][rev_mask[i]][1]);
    }
    else if (val > dp[0][rev_mask[i]][0].first)
    {
        dp[0][rev_mask[i]][1] = dp[0][rev_mask[i]][0];
        dp[0][rev_mask[i]][0] = {val, i};
    }
    else if (val > dp[0][rev_mask[i]][1].first)
    {
        dp[0][rev_mask[i]][1] = {val, i};
    }*/



    for (int i = 1; i <= m; i ++)
        for (int mask = 0; mask < (1 << m); mask ++)
        {
            dp[i][mask][0] = dp[i - 1][mask][0];
            dp[i][mask][1] = dp[i - 1][mask][1];
            if ((mask & (1 << (i - 1))) > 0)
            {
                int new_mask = (mask ^ (1 << (i - 1)));
                int val = dp[i - 1][new_mask][0].first, idx = dp[i - 1][new_mask][0].second;
                if (dp[i][mask][0].second == idx)
                {
                    if (val > dp[i][mask][0].first)
                        dp[i][mask][0].first = val;
                }
                else if (dp[i][mask][1].second == idx)
                {
                    if (val > dp[i][mask][1].first)
                        dp[i][mask][1].first = val;
                    if (dp[i][mask][0].first < dp[i][mask][1].first)
                        swap(dp[i][mask][0], dp[i][mask][1]);
                }
                else if (val > dp[i][mask][0].first)
                {
                    dp[i][mask][1] = dp[i][mask][0];
                    dp[i][mask][0] = {val, idx};
                }
                else if (val > dp[i][mask][1].first)
                {
                    dp[i][mask][1] = {val, idx};
                }

                val = dp[i - 1][new_mask][1].first;
                idx = dp[i - 1][new_mask][1].second;
                if (dp[i][mask][0].second == idx)
                {
                    if (val > dp[i][mask][0].first)
                        dp[i][mask][0].first = val;
                }
                else if (dp[i][mask][1].second == idx)
                {
                    if (val > dp[i][mask][1].first)
                        dp[i][mask][1].first = val;
                    if (dp[i][mask][0].first < dp[i][mask][1].first)
                        swap(dp[i][mask][0], dp[i][mask][1]);
                }
                else if (val > dp[i][mask][0].first)
                {
                    dp[i][mask][1] = dp[i][mask][0];
                    dp[i][mask][0] = {val, idx};
                }
                else if (val > dp[i][mask][1].first)
                {
                    dp[i][mask][1] = {val, idx};
                }

            }
            /// cout << "state " << i << " " << mask << " " << dp[i][mask][0] << " " << dp[i][mask][1] << endl;
        }

    for (int i = 1; i <= n; i ++)
    {
        int two = 0, one = 0, zero = 0;
        for (int j = 0; j < m; j ++)
        {
            if (cnt[j] >= n / 2 + 2)
                two |= (1 << j);
            else if (cnt[j] >= n / 2 + 1)
                one |= (1 << j);
            else if (cnt[j] >= n / 2)
                zero |= (1 << j);
        }

        int mask = 0, rev = 0;
        for (int j = m - 1; j >= 0; j --)
        {
            mask = mask * 2 + (a[i][j]);
            rev = rev * 2 + (1 - a[i][j]);
        }

        int ONE = two | (one & (rev));
        int ZERO = (one & (mask)) | (zero & (rev));

        /**cout << i << " : " << ONE << " : " << ZERO << endl;
        for (int bit = 0; bit < m; bit ++)
            if ((ZERO & (1 << bit)) > 0)
            cout << 1 << " ";
            else
                cout << 0 << " ";
            cout << endl;*/
        int best = dp[m][ZERO][0].first;
        int val = __builtin_popcount(ZERO & rev_mask[i]);
        if (val == best)
            best = dp[m][ZERO][1].first;
        ///cout << i << " : " << val << " " << best << endl;
        cout << __builtin_popcount(ONE) + best << endl;
        continue;
        int ans = 0;
        for (int p = 1; p <= n; p ++)
        {
            if (p == i)
                continue;
            ///cout << "here " << p << " " << ((rev_mask[p])) << endl;
            int cur = __builtin_popcount((rev_mask[p]) & ZERO);
            /**cout << "step " << p << endl;
                    for (int bit = 0; bit < m; bit ++)
            if ((rev_mask[p] & (1 << bit)) > 0)
            cout << 1 << " ";
            else
            cout << 0 << " ";
            cout << endl;*/
            if (cur > __builtin_popcount(ans))
                ans = ((rev_mask[p]) & ZERO);
            ///ans = max(ans, __builtin_popcount((~val_mask[p]) & zero));
        }

        ans |= ONE;
        cout << __builtin_popcount(ans) << endl;



    }

}

int main()
{
    speed();
    solve();
    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