Submission #1130627

#	Time	Username	Problem	Language	Result	Execution time	Memory
1130627		Math4Life2020	Council (JOI23_council)	C++20	100 / 100	931 ms	55260 KiB

council

#include <bits/stdc++.h>
using namespace std;
using ll = long long; using pii = pair<ll,ll>;
const ll Mm = 20; const ll INF = 1e18;
const ll MINV = (1<<Mm)-1;
pii val0[1<<Mm];
array<ll,4> val1[1<<Mm];

pii wt0(pii p1, ll x) {
	if (p1.first==INF) {
		return {x,p1.second};
	} else {
		return {p1.first,x};
	}
}

pii fz0(pii p1, pii p2) {
	//val0 always fills left to right
	if (p1.first==INF && p1.second==INF) {
		return p2;
	}
	if (p1.first!=INF && p1.second==INF) {
		if (p2.first!=p1.first) {
			return {p1.first,p2.first};
		} else {
			return {p1.first,p2.first};
		}
	}
	return p1;
}

array<ll,4> wr1(array<ll,4> a0, pii p1) { //biggest = leftmost
	if (p1.first==INF) {
		return a0;
	}
	if (p1.first==a0[0]) {
		return {a0[0],max(p1.second,a0[1]),a0[2],a0[3]};
	} else if (p1.first==a0[2]) {
		a0 = {a0[0],a0[1],a0[2],max(p1.second,a0[3])};
	} else if (a0[0]==INF) {
		return {p1.first,p1.second,INF,INF};
	} else if (a0[2]==INF) {
		a0 = {a0[0],a0[1],p1.first,p1.second};
	} else {
		if (p1.second>a0[3]) {
			a0 = {a0[0],a0[1],p1.first,p1.second};
		}
	}
	if (a0[1]<a0[3]) {
		a0 = {a0[2],a0[3],a0[0],a0[1]};
	}
	return a0;
}

array<ll,4> fz1(array<ll,4> a0, array<ll,4> a1) {
	return wr1(wr1(a0,{a1[0],a1[1]}),{a1[2],a1[3]});
}

ll rd(array<ll,4> a0, ll x) {
	assert(a0[0]!=INF);
	assert(a0[2]!=INF);
	if (x==a0[0]) {
		return a0[3];
	}
	return a0[1];
}

int main() {
	ll N,M; cin >> N >> M;
	for (int i=0;i<(1<<Mm);i++) {
		val0[i]={INF,INF};
	}
	ll msk[N];
	ll rmsk[N];
	for (ll i=0;i<N;i++) {
		msk[i]=0;
		for (ll j=0;j<M;j++) {
			ll a1; cin >> a1;
			msk[i]+=a1*(1<<j);
		}
		rmsk[i]=MINV^msk[i];
	}
	ll icnt[M];
	for (ll m=0;m<M;m++) {
		icnt[m]=0;
		for (ll i=0;i<N;i++) {
			icnt[m]+=(msk[i]>>m)&1;
		}
	}
	for (int i=0;i<N;i++) {
		val0[rmsk[i]]=wt0(val0[rmsk[i]],i);
	}
	//"sum" over supersets
	for (ll i=0;i<Mm;i++) {
		for (ll B=0;B<(1<<Mm);B++) {
			if ((B>>i)&1) {
				val0[B^(1<<i)]=fz0(val0[B^(1<<i)],val0[B]);
			}
		}
	}
	for (ll B=0;B<(1<<Mm);B++) {
		val1[B]={val0[B].first,0,val0[B].second,0};
		if (val0[B].first!=INF) {
			val1[B][1]=__builtin_popcount(B);
		}
		if (val0[B].second!=INF) {
			val1[B][3]=__builtin_popcount(B);
		}
	}
	//"sum" over subsets
	for (ll i=0;i<Mm;i++) {
		for (ll B=0;B<(1<<Mm);B++) {
			if ((B>>i)&1) {
				val1[B]=fz1(val1[B],val1[B^(1<<i)]);
			}
		}
	}
	for (ll i=0;i<N;i++) {
		ll fcnt[M];
		for (ll m=0;m<M;m++) {
			fcnt[m]=icnt[m]-((msk[i]>>m)&1);
		}
		ll mqry = 0; //query mask
		ll ans = 0; 
		for (ll m=0;m<M;m++) {
			if (fcnt[m]>=((N/2)+1)) {
				ans++;
			} else if (fcnt[m]==(N/2)) {
				mqry += (1<<m);
			}
		}
		ans += rd(val1[mqry],i);
		cout << ans << "\n";
	}
}

• 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