Submission #889670

#	Time	Username	Problem	Language	Result	Execution time	Memory
889670		vjudge1	Council (JOI23_council)	C++17	41 / 100	4054 ms	36136 KiB

council

#include "bits/stdc++.h"

using namespace std;

const int N = 1e5 + 1;

signed main(){
    ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);      

	int n,m;
	cin >> n >> m;
	int a[n][m],s[m],b[n][m];
	for(int i = 0;i  < n;i++){
		for(int j = 0;j < m;j++){
			cin >> a[i][j];
			b[i][j] = a[i][j];
		}
	}
	for(int j = 0;j < m;j++){
		int cnt = 0;
		for(int i = 0;i < n;i++){
			cnt += a[i][j] > 0;
		}
		s[j] = cnt;
//		cout << s[j] << "\n";
	}
	if(n <= 3000){
		
		for(int i = 0;i < n;i++){
			for(int j = 0;j < m;j++){
				a[i][j] = b[i][j];
			}
		}
		for(int i = 0;i < n;i++){
			int ans = 0;
			for(int j = 0;j < n;j++){
				if(i != j){
					int cnt = 0;
					for(int k = 0;k < m;k++){
	//					cout << s[k] << " ";
						if(s[k] - ((a[i][k] == 1) + (a[j][k] == 1)) >= (n) / 2){
							cnt++;
						}
					}
	//				cout << "\n";
					ans = max(ans,cnt);
				}
			}
			cout << ans << "\n";
		}
	} else {
		
		int mp[N] {},l[n + 1] {}; 
		
		vector<int> v;
		
		for(int i =0;i < n;i++){
			int mask = 0;
			for(int j = 0;j < m;j++){
				mask += (1 << j) * a[i][j];
			}
			l[i] = mask;
			mp[mask]++;
			if(mp[mask] == 1){
				v.push_back(mask);
			}
		}	
		int res[N] {};
		
		for(auto mask : v){
			if(mp[mask] == 0){
				continue;
			}
			int ans = 0;
			for(auto msk : v){
				if((mask == msk && mp[mask] < 2) || (mp[msk] == 0)){
					continue;
				}
				int cnt = 0;
				for(int k = 0;k < m;k++){
					int h = msk >> k & 1;
					int z = mask >> k & 1;
					if(s[k] - (h + z) >= n / 2){
						cnt++;
					}
				}
				ans = max(ans,cnt);
			}
			res[mask] = ans;
		}
		for(int i = 0;i < n;i++){
			cout << res[l[i]] << "\n";
		}
		
	}
    
}

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