Submission #1308369

#	Time	Username	Problem	Language	Result	Execution time	Memory
1308369		minh30082008	Council (JOI23_council)	C++20	100 / 100	547 ms	20076 KiB

council

#include<bits/stdc++.h>
#define fi first
#define se second
#define FOR(i, k, n) for(int i = k; i <= n; i++)
#define FOR1(i, k, n) for(int i = k; i >= n; i--)
#define pb push_back
#define fastio ios::sync_with_stdio(0); cin.tie(0); cout.tie(0)
#define vi vector<int>
#define pii pair<int, int>
#define vii vector<pii>
#define ll long long
#define vll vector<ll>
#define pll pair<ll, ll>
#define re return 0
#define mii map<int, int>
#define input "BALLOON.inp"
#define output "BALLOON.out"
#define rf 	freopen(input, "r", stdin); freopen(output, "w", stdout)
using namespace std;
const int maxn = 3e5 + 5;
const int mod = 1e9 + 7;
const int base = 998244353;
const int base1 = 31;
const int SZ = 320;
const ll INF = 1e18;
void add(int &a, int b) 
{
	a += b; 
	if(a >= mod) a -= mod; 
	if(a < 0) a += mod; 
}
mt19937 rd(chrono::steady_clock::now().time_since_epoch().count());
int rand(int l, int r)
{
	return uniform_int_distribution<int>(l, r) (rd);
}
int a[maxn], b[maxn];
pii f[2000000];
pii vt[2000000];
int cnt[25], dem[25];
int main()
{
	fastio;
	int n, m;
	cin >> n >> m;
	FOR(i, 0, (1 << m) - 1)
		f[i].fi = f[i].se = 1e9;
	FOR(i, 1, n)
	{
		a[i] = 0;
		FOR(j, 0, m - 1)
		{
			int x;
			cin >> x;
			a[i] |= (x << j);
			cnt[j] += x;
		}
		b[i] = a[i] ^ ((1 << m) - 1);
		if(!vt[b[i]].fi)
			vt[b[i]].fi = i, f[b[i]].fi = 0;
		else
			vt[b[i]].se = i, f[b[i]].se = 0;
	}
	FOR1(mask, (1 << m) - 1, 0)
	{
		FOR(i, 0, m - 1)
		{
			if((mask >> i) & 1)
				continue;
			int mask1 = mask ^ (1 << i);
			if(!f[mask1].fi)
			{
				if(vt[mask].fi == 0)
				{
					vt[mask].fi = vt[mask1].fi;
					f[mask].fi = 0;
				}
				else
				{
					if(vt[mask].se == 0 && vt[mask1].fi != vt[mask].fi)
					{
						vt[mask].se = vt[mask1].fi;
						f[mask].se = 0;
					}
				}
			}
			if(!f[mask1].se)
			{
				if(vt[mask].fi == 0)
				{
					vt[mask].fi = vt[mask1].se;
					f[mask].fi = 0;
				}
				else
				{
					if(vt[mask].se == 0 && vt[mask1].se != vt[mask].fi)
					{
						vt[mask].se = vt[mask1].se;
						f[mask].se = 0;
					}
				}
			}		
		}
	}
	FOR(mask, 0, (1 << m) - 1)
	{
		FOR(i, 0, m - 1)
		{
			if(!((mask >> i) & 1))
				continue;
			int mask1 = mask ^ (1 << i);
			if(f[mask].fi > f[mask1].fi + 1)
			{
				f[mask].fi = f[mask1].fi + 1;
				vt[mask].fi = vt[mask1].fi;
			}
			if(f[mask].se > f[mask1].fi + 1 && vt[mask].fi != vt[mask1].fi)
			{
				f[mask].se = f[mask1].fi + 1;
				vt[mask].se = vt[mask1].fi;
			}
			if(f[mask].fi > f[mask1].se + 1)
			{
				f[mask].fi = f[mask1].se + 1;
				vt[mask].fi = vt[mask1].se;
			}
			if(f[mask].se > f[mask1].se + 1 && vt[mask].fi != vt[mask1].se)
			{
				f[mask].se = f[mask1].se + 1;
				vt[mask].se = vt[mask1].se;
			}
		}
	}
	FOR(i, 1, n)
	{
		int ans = 0;
		int mask = 0;
		FOR(j, 0, m - 1)
		{
			dem[j] = cnt[j] - ((a[i] >> j) & 1);
			if(dem[j] >= n / 2)
				ans++;
			if(dem[j] == n / 2)
				mask |= (1 << j);
		}
		if(vt[mask].fi == i)
		{
			ans -= f[mask].se;
		}
		else
			ans -= f[mask].fi;
		cout << ans << "\n";
	}
	re;
}

• 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