Submission #1255642

#	Time	Username	Problem	Language	Result	Execution time	Memory
1255642		nerrrmin	Council (JOI23_council)	C++20	25 / 100	139 ms	28212 KiB

council

#include<bits/stdc++.h>
#define endl '\n'
#define pb push_back
using namespace std;
const int maxn = 3e5 + 10, maxm = 22, maxmask = 2002;
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 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] ++;
    }
    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;


          //  cout << mask << " " << mask2 << endl;
            int ans = 0;
            for (int i = 0; i < m; ++ i)
            {
                int bit = min(1, ((1 << i) & mask));
                int bit2 = min(1, ((1 << i) & mask2));

                int now = total[i] - bit - bit2;
                if(now >= n/2)
                {
                    ans ++;
                   /// cout << i << "aaa " << 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: 0 / 15
• Subtask 6: 0 / 22
• Subtask 7: 0 / 22