제출 #1148676

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1148676		AmirAli_H1	Council (JOI23_council)	C++20	100 / 100	698 ms	35328 KiB

council

// In the name of Allah

#include <bits/stdc++.h>
using namespace std;

typedef		long long int			ll;
typedef		long double				ld;
typedef		pair<int, int>			pii;
typedef		pair<ll, ll>			pll;
typedef		complex<ld>				cld;

#define		all(x)					(x).begin(),(x).end()
#define		len(x)					((ll) (x).size())
#define		F						first
#define		S						second
#define		pb						push_back
#define		sep						' '
#define		endl					'\n'
#define		Mp						make_pair
#define		kill(x)					cout << x << '\n', exit(0)
#define		set_dec(x)				cout << fixed << setprecision(x);
#define		file_io(x,y)			freopen(x, "r", stdin); freopen(y, "w", stdout);
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

const int maxn = 3e5 + 4;
const int maxs = (1 << 20) + 4;
const int maxk = 21;

int n, m; int A[maxn];
pair<pii, pii> dp[2][maxs];
int cnt[maxk];

void updx(int j, int mask, pii x) {
	if (x.S == -1) return ;
	if (x > dp[j][mask].F) {
		dp[j][mask].S = dp[j][mask].F;
		dp[j][mask].F = x;
	}
	else if (x > dp[j][mask].S) {
		dp[j][mask].S = x;
	}
}

void solve() {
	cin >> n >> m;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			int x; cin >> x;
			if (x == 1) {
				A[i] ^= (1 << j);
				cnt[j]++;
			}
			else {
				cnt[j]--;
			}
		}
	}

	for (int mask = 0; mask < (1 << m); mask++) {
		dp[0][mask] = Mp(Mp(-1, -1), Mp(-1, -1));
	}
	for (int i = 0; i < n; i++) {
		updx(0, A[i], Mp(0, i));
	}
	for (int j = 0; j < m; j++) {
		for (int mask = 0; mask < (1 << m); mask++) {
			dp[(j & 1) ^ 1][mask] = Mp(Mp(-1, -1), Mp(-1, -1));
		}
		for (int mask = 0; mask < (1 << m); mask++) {
			int T = 0, M = mask;
			if (mask & (1 << j)) {
				T = 1; M ^= (1 << j);
			}
			for (int R = 0; R < 2; R++) {
				if (R == 1) M ^= (1 << j);
				int x = cnt[j];
				if (T == 0) x++;
				else x--;
				if (R == 0) x++;
				else x--;
				auto f = dp[(j & 1)][mask];
				if (x >= 1) {
					if (f.F.S != -1) f.F.F++;
					if (f.S.S != -1) f.S.F++;
				}
				updx((j & 1) ^ 1, M, f.F); updx((j & 1) ^ 1, M, f.S);
			}
		}
	}

	for (int i = 0; i < n; i++) {
		if (dp[m & 1][A[i]].F.S != i) cout << dp[m & 1][A[i]].F.F << endl;
		else cout << dp[m & 1][A[i]].S.F << endl;
	}
}

int main() {
	ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
	
	int T = 1;
	while (T--) {
		solve();
	}
	
	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