Submission #921268

#	Time	Username	Problem	Language	Result	Execution time	Memory
921268		denniskim	Council (JOI23_council)	C++17	100 / 100	3544 ms	131844 KiB

council

#include <bits/stdc++.h>

using namespace std;
typedef int ll;
typedef __int128 lll;
typedef long double ld;
typedef pair<ll, ll> pll;
typedef pair<ld, ld> pld;
#define MAX 9223372036854775807LL
#define MIN -9223372036854775807LL
#define INF 0x3f3f3f3f3f3f3f3f
#define fi first
#define se second
#define fastio ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); cout << fixed; cout.precision(10);
#define sp << " "
#define en << "\n"
#define compress(v) sort(v.begin(), v.end()), v.erase(unique(v.begin(), v.end()), v.end())

ll n, m;
ll A[300010][21];
ll a[300010];
ll siz;
ll dp1[2000010];
ll dp2[2000010][21];
ll cou[21];
ll b[21];
ll pas[21][21];
ll two, one, zero;

int main(void)
{
	fastio
	
	cin >> n >> m;
	
	siz = (1LL << m) - 1;
	
	for(ll i = 1 ; i <= n ; ++i)
	{
		for(ll j = 0 ; j < m ; ++j)
		{
			cin >> A[i][j];
			
			a[i] += (1LL << j) * A[i][j];
			cou[j] += A[i][j];
		}
		
		a[i] ^= siz;
		dp1[a[i]]++;
	}
	
	for(ll i = 0 ; i < m ; ++i)
	{
		for(ll j = siz ; j >= 0 ; --j)
		{
			if(j & (1LL << i))
				dp1[j ^ (1LL << i)] += dp1[j];
		}
	}
	
	for(ll i = 0 ; i <= siz ; ++i)
		dp2[i][__builtin_popcount(i)] += dp1[i];
	
	for(ll i = 0 ; i <= m ; ++i)
	{
		for(ll j = 0 ; j < m ; ++j)
		{
			for(ll k = 0 ; k <= siz ; ++k)
			{
				if(k & (1LL << j))
					dp2[k][i] += dp2[k ^ (1LL << j)][i];
			}
		}
	}
	
	pas[0][0] = 1;
	
	for(ll i = 1 ; i <= 20 ; ++i)
	{
		pas[i][0] = pas[i][i] = 1;
		
		for(ll j = 1 ; j < i ; ++j)
			pas[i][j] = pas[i - 1][j - 1] + pas[i - 1][j];
	}
	
	for(ll i = 0 ; i < m ; ++i)
	{
		if(cou[i] >= n / 2 + 2)
			two |= (1LL << i);
		else if(cou[i] == n / 2 + 1)
			one |= (1LL << i);
		else if(cou[i] == n / 2)
			zero |= (1LL << i);
	}
	
	for(ll i = 1 ; i <= n ; ++i)
	{
		ll ONE = two | (one & a[i]);
		ll ZERO = (one & (~a[i])) | (zero & a[i]);
	
		for(ll j = 0 ; j <= m ; ++j)
			b[j] = dp2[ZERO][j];
		
		ll gap = (a[i] & ZERO);
		ll COU = __builtin_popcount(gap);
		
		for(ll j = 0 ; j <= COU ; ++j)
			b[j] -= pas[COU][j];
		
		ll ans = 0;
		
		for(ll j = m ; j >= 0 ; --j)
		{
			if(b[j])
			{
				ans = max(ans, j);
				break;
			}
		}
		
		cout << ans + __builtin_popcount(ONE) en;
	}
	
	return 0;
}

• 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