Submission #1147404

#	Time	Username	Problem	Language	Result	Execution time	Memory
1147404		Alish	Council (JOI23_council)	C++20	100 / 100	3493 ms	166676 KiB

council

#include <bits/stdc++.h>

using namespace std;

typedef long long int	ll;
typedef pair<int, int>	pii;
typedef pair<ll, ll>	pll;
typedef long double     ld;


#define F		        first
#define S		        second
#define pb		        push_back
#define endl            '\n'
#define Mp              make_pair
#define all(x)          x.begin(), x.end()
#define debug(x)        cerr << #x << " = " << x << endl;
#define fast_io         ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define file_io         freopen("atlarge.in" , "r" , stdin) ;freopen("atlarge.out" , "w" , stdout) ;

const int N = 3e5+23, M=21;

vector<pii> dp[1<<M], dp2[1<<M];
int a[N];
int cnt[M];
int n, m;

vector<pii> Merge(vector<pii> a, vector<pii> b){
    vector<pii> c;
    for (auto pp: a) c.pb(pp);
    for (auto pp: b) c.pb(pp);
    sort(all(c));
    reverse(all(c));
    vector<pii> res;
    for (auto pp: c) {
        if(res.size()==2) break;
        if(res.empty() || (res.back().S!=pp.S)) res.pb(pp);
    }
    return res;
}


int main()
{
    fast_io
    cin>>n>>m;
    for (int i=0; i<n; i++){
        for (int j=0; j<m; j++){
            int x; cin>>x;
            a[i]+=(1<<j)*x;
            cnt[j]+=x;
        }
        dp[(1<<m)-1-a[i]]=Merge(dp[(1<<m)-1-a[i]], {Mp(-1, i)});
    }
    for (int i=0; i<m; i++)for (int mask=0; mask<(1<<m); mask++) if(!(mask>>i&1)) dp[mask]=Merge(dp[mask], dp[mask^(1<<i)]);

    for (int mask=0; mask<(1<<m); mask++){
        int k=__builtin_popcount(mask);
        if(dp[mask].size()>=1) dp2[mask].pb({k, dp[mask][0].S});
        if(dp[mask].size()>=2) dp2[mask].pb({k, dp[mask][1].S});
    }
    for (int i=0; i<m; i++) for (int mask=0; mask<(1<<m); mask++) if(mask>>i&1) dp2[mask]=Merge(dp2[mask], dp2[mask^(1<<i)]);

    int A=0, B=0, C=0;

    for (int i=0; i<m; i++){
        if(cnt[i]==n/2)A+=(1<<i);
        if(cnt[i]==n/2+1) B+=(1<<i);
        if(cnt[i]>=n/2+2) C+=(1<<i);
    }

    for (int i=0; i<n; i++){
        int ok=C|(B&((1<<m)-1-a[i]));
        int can=(B&a[i])|(A&((1<<m)-1-a[i]));
        int ans=__builtin_popcount(ok);
        if(dp2[can][0].S==i) ans+=dp2[can][1].F;
        else ans+=dp2[can][0].F;
        cout<<ans<<endl;
    }
}

• 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