Submission #1308371

#	Time	Username	Problem	Language	Result	Execution time	Memory
1308371		thnhann	Council (JOI23_council)	C++20	100 / 100	555 ms	41400 KiB

council

//#pragma GCC optimize("Ofast,unroll-loops")
//#pragma GCC target("avx,avx2,fma,lzcnt,popcnt")
#include <bits/stdc++.h>
#define ll long long
#define fi first
#define se second
#define pb push_back
#define ii pair<int,int>
#define ill pair<ll,ll>
#define el cout<<'\n'
#define int long long

const ll mod=1e9+7;
const int dx[]={1,0,-1,0},dy[]={0,1,0,-1};
const int nmax=1e6;
const int inf =2e9;

void add(int &a, int b) {
    a += b;
    if (a >= mod) a -= mod;
    if (a < 0) a += mod;
}

template<typename T> void chkmin(T& x, T y) {if(x > y) x = y;}
template<typename T> void chkmax(T& x, T y) {if(x < y) x = y;}

using namespace std;

struct BestPair {
    int val1 = inf, id1 = 0;
    int val2 = inf, id2 = 0;

    void update(int val, int id) {
        if (val < val1) {
            if (id != id1) {
                val2 = val1; id2 = id1;
            }
            val1 = val; id1 = id;
        } else if (val < val2 && id != id1) {
            val2 = val; id2 = id;
        }
    }
    void merge(const BestPair& other) {
        if(other.id1 != 0) update(other.val1, other.id1);
        if(other.id2 != 0) update(other.val2, other.id2);
    }
};

int cnt[25];
bool a[300005][25];
int n, m;
vector<int> p;
int ans = 0;
int type[25];
int id[25];

BestPair dp[1 << 20];

signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);

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

    int k = n / 2;
    int timer = 0;
    for(int i=1; i<=m; i++)
    {
        if(cnt[i] >= k + 2)
        {
            ans++;
        }
        else
        {
            if(cnt[i] == k)
            {
                type[i] = 1;
                p.pb(i);
                id[i] = timer++;
            }
            else if(cnt[i] == k + 1)
            {
                type[i] = 2;
                p.pb(i);
                id[i] = timer++;
            }
        }
    }

    int sz = p.size();
    int full_mask = (1 << sz) - 1;

    for(int i=1;i<=n;i++)
    {
        int mask_person = 0;
        for(int j=0;j<sz;j++)
            if(a[i][p[j]])
        {
            mask_person |= (1<<j);
        }
        int zero = mask_person ^ full_mask;
        dp[zero].update(0,i);
    }

    for(int mask=full_mask;mask>=0;mask--)
    {
        for(int j=0;j<sz;j++)
            if((mask >> j) & 1)
        {
            int submask = mask ^ (1<<j);
            dp[submask].merge(dp[mask]);
        }
    }

    for(int mask=0;mask<=full_mask;mask++)
    {
        for(int j=0;j<sz;j++)
        {
            if((mask >> j) & 1)
            {
                int submask = mask ^ (1<<j);
                if(dp[submask].id1 != 0)
                    dp[mask].update(dp[submask].val1 + 1,dp[submask].id1);
                if(dp[submask].id2 != 0)
                    dp[mask].update(dp[submask].val2 + 1,dp[submask].id2);
            }
        }
    }

    for(int i=1; i<=n; i++)
    {
        int anscur = ans;
        vector<int> bucket;
        for(auto j : p)
        {
            if(a[i][j])
            {
                if(type[j] == 2)
                {
                    bucket.pb(id[j]);
                }
            }
            else
            {
                if(type[j] == 1)
                {
                    bucket.pb(id[j]);
                }
                else
                    anscur++;
            }
        }

        int mask = 0;
        for(auto bit : bucket)
            mask |= (1 << bit);

        anscur += bucket.size();

        int div;
        if(i == dp[mask].id1)
            div = dp[mask].val2;
        else
            div = dp[mask].val1;

        anscur -= div;
        cout << anscur << '\n';
    }
}
//Can i get a kiss? And can u make it last forever?

• 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