제출 #1247519

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1247519		khoianh	Council (JOI23_council)	C++20	100 / 100	391 ms	102240 KiB

council

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int mn = 3e5 + 5, ma = (1 << 20) - 1;
ll n, m,  a[mn][21], s[21], b[mn], req, k, c[ma + 5][2], dp[ma + 5][2], who[ma + 5][2];

void solve(){
	cin >> n >> m;
	req = n/ 2;
//	req = (req 	- 1) / 2 + 1;
	for(int i = 1; i <= n; ++i){
		for(int j = 1; j <= m; ++j) cin >> a[i][j], s[j] += a[i][j], b[i] += a[i][j] * (1LL << (j - 1));
		b[i] ^= ma;
	}
	memset(c, 0, sizeof(c));
	for(int i = 1; i <= n; ++i){
		if(!c[ma ^ b[i]][0]) c[ma ^ b[i]][0] = i;
		else if(!c[ma ^ b[i]][1]) c[ma ^ b[i]][1] = i;
	} 
	for(int k = 0; k < 20; ++k){
		for(int i = 0; i <=	 ma; ++i){
			if(i & (1 << k)){
				if(!c[i ^ (1 << k)][0]) continue;
				if(!c[i][0]) c[i][0] = c[i ^ (1 << k)][0];
				else if(!c[i][1]) c[i][1] = c[i ^ (1 << k)][0];
				if(!c[i ^ (1 << k)][1]) continue;
				if(!c[i][0]) c[i][0] = c[i ^ (1 << k)][1];
				else if(!c[i][1]) c[i][1] = c[i ^ (1 << k)][1];
			}
		}
	}
	for(int i = 0; i <= ma; ++i){
		if(c[ma ^ i][1]) dp[i][0] = dp[i][1] = __builtin_popcount(i), who[i][0] = c[ma ^ i][0], who[i][1] = c[ma ^ i][1];
		else if(c[ma ^ i][0]) dp[i][0] = __builtin_popcount(i), dp[i][1] = -1, who[i][0] = c[ma ^ i][0], who[i][1] = -1;
		else dp[i][0] = dp[i][1] = -1, who[i][0] = -1, who[i][1] = -2; 
	}
	for(int k = 0; k < 20; ++k){
		for(int i = 0; i <= ma; ++i){
///				ll xa = who[i][0], xb = who[i][1];
			if(i & (1 << k)){
				if(dp[i][0] <= dp[i ^ (1 << k)][0]){
					if(who[i ^ (1 << k)][0] == who[i][0]) dp[i][0] = dp[i ^ (1 << k)][0];
					else dp[i][1] = dp[i][0], who[i][1] = who[i][0], dp[i][0] = dp[i ^ (1 << k)][0], who[i][0] = who[i ^ (1 << k)][0];
				} else if(dp[i][1] <= dp[i ^ (1 << k)][0]){
					
					if(who[i ^ (1 << k)][0] == who[i][1] && who[i ^ (1 << k)][0] != who[i][0]) dp[i][1] = dp[i ^ (1 << k)][0];
					else if(who[i ^ (1 << k)][0] != who[i][0]) dp[i][1] = dp[i ^ (1 << k)][0], who[i][1] = who[i ^ (1 << k)][0];
				} 
				if(dp[i][0] <= dp[i ^ (1 << k)][1]){
					if(who[i ^ (1 << k)][1] == who[i][0]) dp[i][0] = dp[i ^ (1 << k)][1];
					else dp[i][1] = dp[i][0], who[i][1] = who[i][0], dp[i][0] = dp[i ^ (1 << k)][1], who[i][0] = who[i ^ (1 << k)][1];
				} else if(dp[i][1] <= dp[i ^ (1 << k)][1]){
					if(who[i ^ (1 << k)][1] == who[i][1] && who[i ^ (1 << k)][1] != who[i][0]) dp[i][1] = dp[i ^ (1 << k)][1];
					else if(who[i ^ (1 << k)][1] != who[i][0]) dp[i][1] = dp[i ^ (1 << k)][1], who[i][1] = who[i ^ (1 << k)][1];
				} 
			}
//			if(who[i][0] == who[i][1]){
//				cout << xa << " " << xb << " " << who[i][0] << " " << who[i][1] << " " << i << "frfr";
//				return;
//			} 
		}
	}
	for(int i = 1; i <= n; ++i){
		ll ans = 0;
		for(int j = 1; j <= m; ++j) s[j] -= a[i][j];
		k = 0;
		for(int j = 1; j <= m; ++j){
			if(s[j] < req) ans += 0;
			else if(s[j] >= req + 1) ans += 1;
			else k += (1LL << (j - 1));
//			, cout << j << " ";
		}
//		cout << ans << " ";
		if(who[k][0] == i) ans += dp[k][1];
		else ans += dp[k][0];
//		cout << who[k][0] << " " << who[k][1] << " " << k << " ";
		for(int j = 1; j <= m; ++j) s[j] += a[i][j];
		cout << ans << "\n";
	}
    return;
}

int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	if(fopen(".INP", "r")) {
		freopen(".INP", "r", stdin);
		freopen(".OUT", "w", stdout);
	}
	int testCase = 1;
	//cin >> testCase;
	while(testCase--) solve();
}

컴파일 시 표준 에러 (stderr) 메시지

council.cpp: In function 'int main()':
council.cpp:87:24: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   87 |                 freopen(".INP", "r", stdin);
      |                 ~~~~~~~^~~~~~~~~~~~~~~~~~~~
council.cpp:88:24: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   88 |                 freopen(".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