Submission #768866

#	Time	Username	Problem	Language	Result	Execution time	Memory
768866		danikoynov	Council (JOI23_council)	C++14	16 / 100	4041 ms	164800 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];
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;

            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]));
                }

    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 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;
}

Compilation message (stderr)

council.cpp: In function 'void solve()':
council.cpp:36:9: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
   36 |         for (int i = 0; i < m; i ++)
      |         ^~~
council.cpp:39:13: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
   39 |             for (int i = 1; i <= n; i ++)
      |             ^~~
council.cpp:81:13: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
   81 |             if (p == i)
      |             ^~
council.cpp:84:17: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
   84 |                 int cur = __builtin_popcount((rev_mask[p]) & ZERO);
      |                 ^~~

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