Submission #1284154

#	Time	Username	Problem	Language	Result	Execution time	Memory
1284154		thuhienne	Council (JOI23_council)	C++20	100 / 100	591 ms	35292 KiB

council

#include <bits/stdc++.h>
using namespace std;

#define re exit(0);
#define thuhien ""
#define fi first
#define se second
#define pii pair <int,int>

int n,m,allmask;
int mask[300009];
int cnt[29];

bool getbit(int mask,int i) {
	return mask >> i & 1;
}

pii f[(1 << 20) + 9],secf[(1 << 20) + 9];
//fi = min builtin popcount cua 1 nut ma lam cha cua i

pii dp[(1 << 20) + 9],secdp[(1 << 20) + 9];
//dpi = min builtin popcount cua i and voi mot so nao do trong ai
//-> dp i thuoc vao 2 loai:
//Loai 1: ton tai mot vi tri j nao do ma bit j cua dp i va bit j cua i deu = 0
//-> dap an se thuoc mot trong cac cha cua i
//Loai 2: voi moi vi tri j thi viec ca 2 dieu tren khong xay ra dong thoi
//-> voi moi vi tri j ma bit j cua i = 0 thi bit j cua sol phai bang 1 -> tap cha cua phan bu

void getbetterf(int mask,pair <int,int> val) {
	if (f[mask].second > val.second) {
		secf[mask] = f[mask];
		f[mask] = val;
	} else if (secf[mask].second > val.second && val.first != f[mask].first) secf[mask] = val;
}
void getbetterdp(int mask,pair <int,int> val) {
	if (dp[mask].second > val.second) {
		secdp[mask] = dp[mask];
		dp[mask] = val;
	} else if (secdp[mask].second > val.second && val.first != dp[mask].first) secdp[mask] = val;
}

int main() {
  ios_base::sync_with_stdio(0);cin.tie(nullptr);
	if (fopen(thuhien".inp","r")) {
		freopen(thuhien".inp","r",stdin);
		freopen(thuhien".out","w",stdout);
	}

	cin >> n >> m;
	allmask = (1 << m) - 1;
	
	for (int i = 0;i <= allmask;i++) f[i] = secf[i] = {-1,1e9};
	
	dp[allmask] = secdp[allmask] = {-1,1e9};
	
	for (int i = 1;i <= n;i++) {
		for (int j = 0;j < m;j++) {
			int a;cin >> a;
			mask[i] += a << j;
			
			if (a) cnt[j]++;
		}
		getbetterf(mask[i],{i, __builtin_popcount(mask[i]) });
		
		getbetterdp(allmask,{i, __builtin_popcount(mask[i] & allmask) });
//		cout << mask[i] << '\n';
	}
	
	
	for (int mask = allmask;mask >= 0;mask--) {
		for (int i = 0;i < m;i++) if (!getbit(mask,i)) {
			getbetterf(mask,f[mask + (1 << i)]);
			getbetterf(mask,secf[mask + (1 << i)]);
		}
		
//		cout << mask << " " << f[mask] << '\n';
	}
	for (int mask = allmask - 1;mask >= 0;mask--) {
		dp[mask] = secdp[mask] = {-1,1e9};
		for (int i = 0;i < m;i++) if (!getbit(mask,i)) {
			getbetterdp(mask,dp[mask + (1 << i)]);
			getbetterdp(mask,secdp[mask + (1 << i)]);
		}
		
		int bumask = allmask - mask;
		getbetterdp(mask,make_pair(f[bumask].first,f[bumask].second - __builtin_popcount(bumask)));
		getbetterdp(mask,make_pair(secf[bumask].first,secf[bumask].second - __builtin_popcount(bumask)));
		
//		cout << mask << " " << dp[mask] << '\n';
	}
	
	
	int minimum = n/2;
	
	for (int i = 1;i <= n;i++) {
		int loai = 0,maska = 0;
		
		for (int j = 0;j < m;j++) {
			if (cnt[j] - getbit(mask[i],j) < minimum) loai++;
			else if (cnt[j] - getbit(mask[i],j) == minimum) maska += (1 << j);
		}
		
		loai += (dp[maska].first == i ? secdp[maska].second : dp[maska].second);
		
		cout << m - loai << "\n";
	}
}

Compilation message (stderr)

council.cpp: In function 'int main()':
council.cpp:45:24: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   45 |                 freopen(thuhien".inp","r",stdin);
      |                 ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
council.cpp:46:24: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   46 |                 freopen(thuhien".out","w",stdout);
      |                 ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~

• 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