Submission #1306449

#	Time	Username	Problem	Language	Result	Execution time	Memory
1306449		mohammadsam	Council (JOI23_council)	C++20	100 / 100	670 ms	380584 KiB

council

/*
    in the name of god
*/
//#pragma GCC optimize("Ofast,O3,unroll-loops")
//#pragma GCC target("avx,avx2,fma")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4.1,sse4.2,sse4a,avx,avx2,popcnt,tune=native")

#include <bits/stdc++.h>

using namespace std;

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

#define File          freopen("input.txt", "r", stdin); freopen("output.txt", "w", stdout);
#define all(V)        V.begin(),V.end()
#define setprec(x)    fixed << setprecision(x)
#define Mp(a,b)       make_pair(a,b)
#define len(V)        (int)(V.size())
#define sep           ' '
#define endl          '\n'
#define pb            push_back
#define fi            first
#define sec           second
#define popcount(x)   __builtin_popcount(x)
#define lid           u<<1
#define rid           (lid)|1
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());

const ll N = 3e5 + 10,M=20,SQ=320,LOG=31;
const ll inf = 2e9 , MD = 1e9 + 7;

inline ll md(ll x){ x %= MD; return (x < 0 ? x + MD : x);}
int n , m ;
int arr[N];
pii dp1[M+1][1<<M],dp2 [M+1][1<<M];
int cnt[N];
vector<int> comp[1<<M];
int32_t main() {
    ios_base::sync_with_stdio(false);cout.tie(0);cin.tie(0);
    cin >> n >> m ;
    for(int i =1 ;i <= n ;i++){
        for(int j = 0 ; j < m;j++){
            int x;
            cin >> x;
            cnt[j] += x;
            arr[i] += x*(1<<j);
        }
        comp[arr[i]].pb(i);
    }
    int lim = n/2;
    for(int mask = 0;mask < (1<<m);mask++){
        dp1[0][mask] = dp2[0][mask] = {inf,-1};
        if(len(comp[mask]) >= 1){
            dp1[0][mask] = {0,comp[mask][0]};
        }
        if(len(comp[mask]) >= 2){
            dp2[0][mask] = {0,comp[mask][1]};
        }
    }
    auto update = [&](pii& a,pii& b,pii x){
        if(x.fi <= a.fi){
            b = a;
            a = x;
        }
        else if(x.fi <= b.fi) b = x;
    };
    for(int j = 1;j <= m;j++){
        
        for(int mask = 0;mask < (1<<m);mask++){
            dp1[j][mask] = dp2[j][mask] = {inf,-1};
            if((mask&(1<<(j-1))) == 0) {
                update(dp1[j][mask],dp2[j][mask],dp1[j-1][mask]);
                update(dp1[j][mask],dp2[j][mask],dp2[j-1][mask]);
                update(dp1[j][mask],dp2[j][mask],dp1[j-1][mask^(1<<(j-1))]);
                update(dp1[j][mask],dp2[j][mask],dp2[j-1][mask^(1<<(j-1))]);
            }
            else{
                update(dp1[j][mask],dp2[j][mask],dp1[j-1][mask^(1<<(j-1))]);
                update(dp1[j][mask],dp2[j][mask],dp2[j-1][mask^(1<<(j-1))]);
                update(dp1[j][mask],dp2[j][mask],{dp1[j-1][mask].fi + 1,dp1[j-1][mask].sec});
                update(dp1[j][mask],dp2[j][mask],{dp2[j-1][mask].fi + 1,dp2[j-1][mask].sec});
            }
        }   
    }
    for(int i =1 ;i <=n ;i++){
        for(int j = 0 ; j <  m;j++){
            cnt[j] -= ((arr[i]>>j)&1);
        }
        int mask = 0;
        int tmp = 0;
        for(int j = 0 ; j < m;j++){
            if(cnt[j] == lim) mask += (1<<j);
            if(cnt[j] >= lim) tmp++;
        }

        if(dp1[m][mask].sec != i) cout << tmp - dp1[m][mask].fi << endl;
        else cout << tmp - dp2[m][mask].fi << endl;
        for(int j = 0 ; j <  m;j++){
            cnt[j] += ((arr[i]>>j)&1);
        }
    }


    return 0;
}

• 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