oj.uz

답안 #1086840

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1086840 2024-09-11T14:54:27 Z coldbr3w Council (JOI23_council) C++17
0 / 100
 206 ms 348 KB 
#include <bits/stdc++.h>
using namespace std;

#define ll int
#define pll pair<int, int>
#define pb push_back
#define F first
#define S second  
#define all(x) (x).begin(), (x).end()

const ll N = 2e6 + 100;
const ll inf = 1e9;
const ll mod = 1e9 + 7;
const ll block = 350;
ll n,m;
ll a[N][21], res[N], cnt[N], dp[N], mp[N];
pll mn[N];
void to_thic_cau(){
	cin >> n >> m;
	for(int i = 0; i < (1 << m);i++) mn[i] = {inf, inf};
	for(int i = 1; i <= n;i++){
		ll msk = 0;
		for(int j = 0; j < m;j++){
			cin >> a[i][j];
			if(a[i][j] == 1) cnt[j]++, msk |= (1 << j);
		}
		dp[msk]++;
		mp[msk]++;
	}
	for(int i = 0; i < m;i++){
		for(int msk = 0; msk < (1 << m);msk++) if(msk & (1 << i)) dp[msk] += dp[msk ^ (1 << i)];
	}
	for(int msk = 0; msk < (1 << m);msk++){
		ll inv_msk = ((1 << m) - 1) ^ msk;
		for(int sub = msk; sub >= 0;sub = (sub - 1) & msk){
			ll cur = sub | inv_msk;
			ll c = __builtin_popcount(sub);
			ll d = 0;
			for(int final_msk = cur; final_msk >= 0; final_msk = (final_msk - 1) & cur){
				if(((final_msk) & sub) == sub) d++;
				if(final_msk == 0) break;
			}
			if(d >= 1){
				if(c < mn[msk].F) mn[msk].S = mn[msk].F, mn[msk].F = c;
				else if(c < mn[msk].S) mn[msk].S = c;
			}
			if(d >= 2){
				mn[msk].F = min(mn[msk].F, c); mn[msk].S = min(mn[msk].S, c);
			}
			if(sub == 0) break;
		}
	}
	for(int i = 1; i <= n;i++){
		ll msk = 0, cur = 0, res = 0;
		for(int j = 0; j < m;j++){
			if(a[i][j] == 1) cnt[j]--;
			if(cnt[j] == n / 2) msk |= (1 << j), res++;
			else if(cnt[j] > n / 2) res++;
		}
		for(int j = 0; j < m;j++) if((msk & (1 << j)) && a[i][j] == 1) cur++;
		if(cur == mn[msk].F) res -= mn[msk].S;
		else res -= mn[msk].F;
		for(int j = 0; j < m;j++) if(a[i][j] == 1) cnt[j]++;
		cout << res << "\n";
	}
}

signed main()   
{ 
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	ll tc = 1;
	//cin >> tc;
	while(tc--) to_thic_cau();
}

Subtask #1
0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 348 KB Output is correct
2 Incorrect 206 ms 348 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 348 KB Output is correct
2 Incorrect 206 ms 348 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0 / 6.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 348 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 19.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 348 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 348 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
0 / 22.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 348 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #7
0 / 22.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 348 KB Output is correct
2 Incorrect 206 ms 348 KB Output isn't correct
3 Halted 0 ms 0 KB -