Submission #1284097

#	Time	Username	Problem	Language	Result	Execution time	Memory
1284097		thuhienne	Council (JOI23_council)	C++20	6 / 100	37 ms	2988 KiB

council

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

#define re exit(0);
#define thuhien ""

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

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

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

int dp[(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

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] = -1;
	dp[allmask] = 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]++;
		}
		f[mask[i]] = __builtin_popcount(mask[i]);
		dp[allmask] = min(dp[allmask],__builtin_popcount(allmask & mask[i]));
//		cout << mask[i] << '\n';
	}
	
	for (int mask = allmask;mask >= 0;mask--) {
		if (f[mask] != -1) continue;
		
		f[mask] = 1e9;
		for (int i = 0;i < m;i++) if (!getbit(mask,i)) f[mask] = min(f[mask],f[mask + (1 << i)]);
		
//		cout << mask << " " << f[mask] << '\n';
	}
	
	for (int mask = allmask - 1;mask >= 0;mask--) {
		dp[mask] = 1e9;
		for (int i = 0;i < m;i++) if (!getbit(mask,i)) dp[mask] = min(dp[mask],dp[mask + (1 << i)]);
		
		int bumask = allmask - mask;
		dp[mask] = min(dp[mask],f[bumask] - __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];
		
		cout << m - loai << "\n";
	}
}

Compilation message (stderr)

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

• 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