結果

問題 No.3410 Happiest Art
コンテスト
ユーザー Unbakedbread
提出日時 2025-12-12 18:21:25
言語 C++23
(gcc 13.3.0 + boost 1.89.0)
結果
WA  
実行時間 -
コード長 1,351 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 3,438 ms
コンパイル使用メモリ 293,848 KB
実行使用メモリ 814,656 KB
最終ジャッジ日時 2025-12-16 23:31:59
合計ジャッジ時間 6,684 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 6 WA * 5 MLE * 1 -- * 32
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

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

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

int main(void) {
	int N, U, H, W;
	cin >> N >> U >> H >> W;
	int HW = H * W;
	
	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, string> ms;
	for(int x = 0; x < N; ++x) {
		int F;
		cin >> F;
		string T;
		for(int i = 0; i < H; ++i) {
			string S;
			cin >> S;
			T += S;
		}
		
		ll h = 0;
		for(int i = 0; i < HW; ++i) if(T[i] == '#') {
			h += p2[i];
			if(h >= mod) h -= mod;
		}
		
		int tri = (x < U ? 1 : -1);
		if(m.find(h) == m.end()) ms[h] = T;
		m[h] += tri;
		
		if(F == 0) continue;
		for(int i = 0; i < HW; ++i) {
			ll hi = h + (T[i] == '#' ? -1 : 1) * p2[i];
			if(hi < 0) hi += mod;
			if(hi >= mod) hi -= mod;
			
			if(m.find(hi) == m.end()) ms[hi] = T;
			m[hi] += tri;
		}
	}
	
	ll max_h = -1;
	for(int i = 0; i < (1 << min(25, HW)); ++i) if(m.find(i) == m.end()) {
		max_h = i;
		break;
	}
	
	m[-1] = -1e9;
	for(auto [h, val] : m) if(m[max_h] < val) max_h = h;
	
	string ans(HW, '.');
	if(ms.find(max_h) != ms.end()) ans = ms[max_h];
	else for(int i = 0; i < HW; ++i) if(max_h >> i & 1) ans[i] = '#';
	
	cout << m[max_h] << "\n";
	for(int i = 0; i < H; ++i) cout << ans.substr(i * W, W) << "\n";
	return 0;
}
0