Submission #1256334

#	Time	Username	Problem	Language	Result	Execution time	Memory
1256334		nerrrmin	Council (JOI23_council)	C++20	40 / 100	4096 ms	17852 KiB

council

#include<bits/stdc++.h>
#define endl '\n'
#define pb push_back
using namespace std;
const int maxn = 3e5 + 10, maxm = 13, maxmask = 17002;
void speed()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
}
int n, m;
int a[maxn][maxm];
vector < int > u[maxm];
int fix[maxn];

int res[maxn];
int cnt[maxmask];
int total[maxm];

int is[maxn];
int mp[maxmask];
int main()
{
    speed();

    cin >> n >> m;


    for (int i = 1; i <= n; ++ i)
    {
        int mask = 0;
        for (int j = 0; j < m; ++ j)
        {
            cin >> a[i][j];
            if(a[i][j])mask = (mask | (1 << j));
            if(a[i][j])
            {
                total[j] ++;
            }
        }

      //  cout << i << " " << mask << endl;
        is[i] = mask;
        cnt[mask] ++;
    }

    int maskout1 = 0, maskout2 = 0;

    int cout1 = 0, cout2 = 0;
    int sure = 0;
    for (int i = 0; i < m; ++ i)
    {
        if(total[i] == n/2)
        {
            maskout1 = (maskout1 | (1 << i));
            cout1 ++;
        }
        else if(total[i] == n/2 + 1)
        {
            maskout2 = (maskout2 | (1 << i));
            cout2 ++;
        }
        else if(total[i] >= n/2 + 2)sure ++;
    }

    for (int mask = 0; mask < (1 << m); ++ mask)
    {
        for (int i = 0; i < m; ++ i)
        {
            if((mask & (1 << i)))mp[mask] ++;
        }
    }
    for (int mask = 0; mask < (1 << m); ++ mask)
    {
        for (int mask2 = 0; mask2 < (1 << m); ++ mask2)
        {
            if(!cnt[mask] || !cnt[mask2])continue;
            if(mask == mask2 && cnt[mask] < 2)continue;

            int one = (mask | mask2);
            int both = (mask & mask2);

            int out1 = (maskout1 & one);
            int out2 = (maskout2 & both);
          //  cout << mask << " " << mask2 << endl;
            int ans = sure + (cout1 - mp[out1]) + (cout2 - mp[out2]);
           // cout << sure << " " << mp[out1] << "  " << mp[out2] << endl;

            res[mask] = max(res[mask], ans);
            res[mask2] = max(res[mask2], ans);
        }
    }

    for (int i = 1; i <= n; ++ i)
    {
        int mask = is[i];
        cout << res[mask] << endl;
    }
    return 0;
}

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