結果

問題 No.3410 Happiest Art
コンテスト
ユーザー Unbakedbread
提出日時 2025-12-12 19:30:26
言語 C++23
(gcc 13.3.0 + boost 1.89.0)
結果
AC  
実行時間 1,303 ms / 4,000 ms
コード長 1,760 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 3,714 ms
コンパイル使用メモリ 295,132 KB
実行使用メモリ 89,668 KB
最終ジャッジ日時 2025-12-16 23:32:14
合計ジャッジ時間 10,725 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 44
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

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

using ll = long long;
constexpr ll mod = 1e18 + 3;

int main(void) {
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	cout.tie(nullptr);
	
	int N, U, H, W;
	cin >> N >> U >> H >> W;
	int HW = H * W;
	
	vector<int> F(N);
	vector<string> S(N);
	for(int x = 0; x < N; ++x) {
		cin >> F[x];
		for(int i = 0; i < H; ++i) {
			string T;
			cin >> T;
			S[x] += T;
		}
	}
	
	vector<ll> p2(HW);
	p2[0] = 1;
	for(int i = 1; i < HW; ++i) {
		p2[i] = p2[i - 1] * 2;
		if(p2[i] >= mod) p2[i] -= mod;
	}
	
	unordered_map<ll, int> m;
	unordered_map<ll, pair<int, int>> ms;
	for(int x = 0; x < N; ++x) {
		ll h = 0;
		for(int i = 0; i < HW; ++i) if(S[x][i] == '#') {
			h += p2[i];
			if(h >= mod) h -= mod;
		}
		
		if(m.find(h) == m.end()) ms[h] = make_pair(x, -1);
		m[h] += (x < U ? 1 : -1);
		
		if(F[x] == 0) continue;
		for(int i = 0; i < HW; ++i) {
			ll hi = h + (S[x][i] == '#' ? -1 : 1) * p2[i];
			if(hi < 0) hi += mod;
			if(hi >= mod) hi -= mod;
			
			if(m.find(hi) == m.end()) ms[hi] = make_pair(x, i);
			m[hi] += (x < U ? 1 : -1);
		}
	}
	
	ll val_max = -1e9, h_max = -1;
	pair<int, int> ans;
	for(int i = 0; i < (1 << min(25, HW)); ++i) if(m.find(i) == m.end()) {
		val_max = 0;
		h_max = i;
		ans = make_pair(-1, -1);
		break;
	}
	
	for(auto [h, val] : m) if(val_max < val) {
		val_max = val;
		h_max = h;
		ans = ms[h];
	}
	
	cout << val_max << "\n";
	
	auto [x, p] = ans;
	if(x == -1) {
		for(int i = 0; i < HW; ++i) {
			if(h_max >> i & 1) cout << '#';
			else cout << '.';
			if(i % W == W - 1) cout << "\n";
		}
	}
	else {
		for(int i = 0; i < HW; ++i) {
			if(i != p) cout << S[x][i];
			else if(S[x][i] == '#') cout << '.';
			else cout << '#';
			if(i % W == W - 1) cout << "\n";
		}
	}
	return 0;
}
0