Submission #1133584

#	Time	Username	Problem	Language	Result	Execution time	Memory
1133584		mychecksedad	Council (JOI23_council)	C++20	6 / 100	466 ms	95524 KiB

council

/* Author : Mychecksdead  */
#include <bits/stdc++.h>
using namespace std;
#define ll long long int
#define MOD (1000000000+7)
#define pb push_back
#define all(x) x.begin(), x.end()
#define en cout << '\n'
#define ff first
#define ss second
#define pii pair<int,int>
#define vi vector<int>
const int N = 2e6+100, M = 1e5+10, K = 22, MX = 70;
const ll INF = 2e18;

int n, m, dp[N];
vector<pii> DP[N];
int get(int mask, int pos){
	if(DP[mask].size() == 0) return __builtin_popcount(mask);
	if(DP[mask].size() == 1){
		if(DP[mask][0].ss == pos) return __builtin_popcount(mask);
		return DP[mask][0].ff;
	}
	auto x = DP[mask][0];
	auto y = DP[mask][1];
	if(x.ss == pos || y.ss == pos){
		if(x.ss == pos) return y.ff;
		return x.ff;
	}
	return min(x.ff, y.ff);
}
void solve(){
	cin >> n >> m;
	vector<int> tot(m);
	for(int i = 1; i <= n; ++i){
		dp[i] = 0;
		for(int j = 0; j < m; ++j){
			int x; cin >> x;
			dp[i] += x*(1<<j);
			if(x==1) tot[j] += 1;
		}
		int s = ((1<<m)-1)^dp[i];
		DP[s].pb(pii{0, i});
		if(DP[s].size()>2) DP[s].pop_back();
	}	
	for(int i = (1<<m)-1; i >= 0; --i){
		if(DP[i].size() == 2) continue;
		for(int j = 0; j < m; ++j){
			if((i&(1<<j))==0){
				for(int l = 0; l < DP[i^(1<<j)].size() && DP[i].size() < 2; ++l) DP[i].pb(DP[i^(1<<j)][l]);
			}
			if(DP[i].size() == 2) break;
		}
	}
	for(int i = 0; i < (1<<m); ++i){
		for(int j = 0; j < m; ++j){
			if((1<<j)&i){
				int o = i^(1<<j);
				for(auto x: DP[o]){
					x.ff++;
					bool bad = 0;
					for(auto &y: DP[i]){
						if(y.ss == x.ss){
							bad = 1;
							if(y.ff > x.ff) y.ff = x.ff;
						}
					}
					if(!bad)
						DP[i].pb(x);
				}
				if(DP[i].size()>2){
					sort(all(DP[i]));
					while(DP[i].size()>2) DP[i].pop_back();
				}	
			}
		}
	}
	// for(int i = 0; i < (1<<m); ++i){
	// 	cout << i << ": ";
	// 	for(auto [x,y]: DP[i]) cout << "("<<x<<", " << y << "), ";
	// 	en;
	// }
	int k = (n-2)/2+1;
	for(int i = 1; i <= n; ++i){
		int mask = 0, ans = 0;
		for(int j = 0; j < m; ++j){
			if((1<<j)&dp[i]){
				if(tot[j] >= k + 2){
					++ans;
				}else if(tot[j] == k + 1){
					mask += (1<<j);
				}
			}else{
				if(tot[j] >= k + 1) ++ans;
				else if(tot[j] == k) mask += (1<<j);
			}
		}
		// cout << ans << ' ' << mask << ' ' << __builtin_popcount(mask) << ' ' << get(mask ,i) << ' ';
		cout << ans + __builtin_popcount(mask) - get(mask, i) << '\n';
	}
}


int main(){
  cin.tie(0); ios::sync_with_stdio(0);
  int tt = 1, aa;
  // freopen("in.txt", "r", stdin);
  // freopen("out.txt", "w", stdout);
  while(tt--){
    solve();
  }
  cerr<<"time taken : "<<(float)clock()/CLOCKS_PER_SEC<<" seconds\n";
  return 0;
} 

• 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