Submission #918374

#	Time	Username	Problem	Language	Result	Execution time	Memory
918374		gs25	Council (JOI23_council)	C++17	62 / 100	311 ms	68948 KiB

council

#include <bits/stdc++.h> 

using namespace std; 


void __print(int x) { cerr << x; }
void __print(long x) { cerr << x; }
void __print(long long x) { cerr << x; }
void __print(unsigned x) { cerr << x; }
void __print(unsigned long x) { cerr << x; }
void __print(unsigned long long x) { cerr << x; }
void __print(float x) { cerr << x; }
void __print(double x) { cerr << x; }
void __print(long double x) { cerr << x; }
void __print(char x) { cerr << '\'' << x << '\''; }
void __print(const char *x) { cerr << '\"' << x << '\"'; }
void __print(const string &x) { cerr << '\"' << x << '\"'; }
void __print(bool x) { cerr << (x ? "true" : "false"); }

template <typename T, typename V> void __print(const pair<T, V> &x) {
  cerr << '{';
  __print(x.first);
  cerr << ", ";
  __print(x.second);
  cerr << '}';
}
template <typename T> void __print(const T &x) {
  int f = 0;
  cerr << '{';
  for (auto &i : x)
    cerr << (f++ ? ", " : ""), __print(i);
  cerr << "}";
}
void _print() { cerr << "]\n"; }
template <typename T, typename... V> void _print(T t, V... v) {
  __print(t);
  if (sizeof...(v))
    cerr << ", ";
  _print(v...);
}
#ifndef ONLINE_JUDGE
#define dbg(x...)                                                              \
  cerr << "\e[91m" << __func__ << ":" << __LINE__ << " [" << #x << "] = [";    \
  _print(x);                                                                   \
  cerr << "\e[39m" << endl;
#else
#define dbg(x...)
#endif	

#define rrep(i,n) for(int i=1; i<=n; i++)
#define rep(i,n) for(int i=0; i<n; i++)
#define all(v) (v).begin(), (v).end() 
#define ff first 
#define ss second 
#define pb push_back

int popcnt(int x){
	assert(x>=0);
	return __builtin_popcount(x);
}

int N,M; 

const int MAXN = 300100; 
int x[MAXN]; 
int p[30]; 

int cnt[MAXN]; 
long long dp[22][3000000]; 
int comb[300][300]; 


void solve(){
	comb[1][0] = 1; 
	comb[1][1] = 1; 
	for(int i=2; i<=22; i++){
		for(int j=0; j<=i; j++){
			comb[i][j] = comb[i-1][j]+(j!=0 ? comb[i-1][j-1] : 0); 
		}
	}
	cin >> N >> M; 
	int k = N/2; 
	const int MSK = (1<<M) - 1; 
	rep(i,N){
		rep(j,M){
			int a; cin >> a; 
			if(a==0) continue; 
			p[j] += a; 
			x[i] |= (1<<j); 
		}
		x[i] = (~x[i])&MSK; 
	}
	int zeros=0, ones=0, twos=0; 
	rep(j,M){
		if(p[j]>=k+2) zeros |= (1<<j); 
		if(p[j]==k+1) ones |= (1<<j); 
		if(p[j]==k) twos |= (1<<j); 
	}
	rep(i,N) cnt[x[i]]++; 
	for(int i=0; i<M; i++){
		for(int j=0; j<=MSK; j++){
			if( (j & (1<<i)) ==0) {
				cnt[j] += cnt[j^(1<<i)]; 
			}
		}
	}
	for(int j=0; j<= MSK; j++) dp[popcnt(j)][j] = cnt[j]; 
	for(int i=0; i<M; i++){
		for(int j=0; j<=MSK; j++){
			if(j&(1<<i)){
				rep(k,M) dp[k][j] += dp[k][j^(1<<i)]; 
			}
		}
	}
	rep(i,N){
		int tmp = (ones&(~x[i])) | (twos&(x[i]));
		// tmp maximize tmp | x[j];
		int MM = 0;   
		bool flag = false; 
		long long sum = 0, first_big=0, id=0; 
		for(int k=M; k>=0; k--){
			if(!flag && dp[k][tmp]>0LL){
				if(popcnt(tmp&x[i])!=k){
					MM = k; break; 
				}
				flag=true; 
				if(dp[k][tmp]>1){
					MM = k; break; 
				}
				first_big=k; 
				sum = 1;
				id = 1;
				continue;  
			}
			if(flag){
				assert(id<30 && first_big < 30);
				sum = comb[first_big][id++];
				if(dp[k][tmp]>sum){
					MM = k; break; 
				} 
			}
		}
		cout << MM + popcnt(zeros|(ones&x[i])) << "\n"; 
	}
}

int32_t main(void){
	ios::sync_with_stdio(false); 
	cout.tie(nullptr); 
	cin.tie(nullptr);
	int t =1; // cin >> t; 
	while(t--) solve(); 
}

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