Submission #1249087

#	Time	Username	Problem	Language	Result	Execution time	Memory
1249087		poat	Council (JOI23_council)	C++17	6 / 100	219 ms	33284 KiB

council

// #pragma GCC optimize("Ofast")
// #pragma GCC target("popcnt")
 
#include <bits/stdc++.h>
using namespace std;
 
#define int long long
const int N = 2e6, K = 29, inf = 1e16, mod = 998244353;
const double eps = 1e-6;

int dp[N][2];
int ind[N][2];

void add(int mask, int id, int val)
{   
    if(id == ind[mask][0])
    {
        dp[mask][0] = max(dp[mask][0], val);
        return;
    }
    else if(id == ind[mask][1])
    {
        dp[mask][1] = max(dp[mask][1], val);
        return;
    }

    if(val > dp[mask][0])
    {
        dp[mask][1] = dp[mask][0];
        ind[mask][1] = ind[mask][0];

        dp[mask][0] = val;
        ind[mask][0] = id;
    }
    else if(val > dp[mask][1])
    {
        dp[mask][1] = val;
        ind[mask][1] = id;
    }
}

void solve()
{  
    int n, m;
    cin >> n >> m;

    int arr[n][m], cnt[m] = {};
    for(int i = 0; i < n; i++)
    {
        for(int j = 0; j < m; j++)
        {
            cin >> arr[i][j];
            cnt[j] += arr[i][j];
        }
    }

    for(int i = 0; i < (1 << m); i++)
        ind[i][0] = ind[i][1] = -1;
    
    int ms[n] = {}, nms[n] = {};

    vector<int> ans(n, 0);
    
    for(int i = 0; i < n; i++)
    {
        for(int j = 0; j < m; j++)
        {   
            if(cnt[j] - arr[i][j] == n / 2)
                ms[i] += (1 << j);
            else if(cnt[j] - arr[i][j] > n / 2)
                ans[i]++;

            nms[i] = nms[i] + (1 << j) * (arr[i][j] == 0);
        }
        
        add(nms[i], i, __builtin_popcount(nms[i]));
    }

    // cout << "&";
    // for(int i = 0; i < n; i++)
    //     cout << ans[i] << ' ';
    
    // cout << "\n";
    


    // cout << "\n";

    // for(int i = 0; i < n; i++)
    // {
    //     cout << "#";
    //     for(int k = 0; k < m; k++)
    //         cout << ((ms[i] >> k) & 1);
    //     cout << "\n";
    // }

    // cout << "\n";
    
    // for(int i = 0; i < n; i++)
    // {
    //     cout << "!";
    //     for(int k = 0; k < m; k++)
    //         cout << ((nms[i] >> k) & 1);
    //     cout << "\n";
    // }

    // cout << "\n\n";


    for(int mask = (1 << m) - 1; mask >= 0; mask--)
    {
        for(int k = 0; k < m; k++)
        {
            if(((mask >> k) & 1) == 0)
                continue;
            
            int nmask = mask - (1 << k);

            if(ind[mask][0] != -1)
                add(nmask, ind[mask][0], __builtin_popcount(nmask));
            if(ind[mask][1] != -1)
                add(nmask, ind[mask][1], __builtin_popcount(nmask));
        }
    }


    for(int mask = 0; mask < (1 << m); mask++)
    {
        for(int k = 0; k < m; k++)
        {
            if((mask >> k) & 1)
                continue;
                
            int nmask = mask + (1 << k);

            if(ind[mask][0] != -1)
                add(nmask, ind[mask][0], dp[mask][0]);
            if(ind[mask][1] != -1)
                add(nmask, ind[mask][1], dp[mask][1]);
        }
    }


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

        if(ind[mask][0] == i)
            cout << ans[i] + dp[mask][1] << "\n";
        else
            cout << ans[i] + dp[mask][0] << "\n";
    }


    


}

signed main()
{   
    // txt;
    ios_base::sync_with_stdio(false), cin.tie(0), cout.tie(0);
    int T = 1;
    for(; T--; solve());
}

/*

*/

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