結果

問題 No.3410 Happiest Art
コンテスト
ユーザー GOTKAKO
提出日時 2025-12-17 00:21:03
言語 C++17
(gcc 13.3.0 + boost 1.89.0)
結果
TLE  
実行時間 -
コード長 2,907 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 2,792 ms
コンパイル使用メモリ 211,132 KB
実行使用メモリ 12,840 KB
最終ジャッジ日時 2025-12-17 00:21:29
合計ジャッジ時間 25,030 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 25 TLE * 1 -- * 18
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

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

random_device rnd;
mt19937 mt(rnd());

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    int N,U; cin >> N >> U;
    int H,W; cin >> H >> W;
    vector<int> F(N);
    vector<vector<string>> S(N,vector<string>(H));
    for(int i=0; i<N; i++){
        int f; cin >> f; F.at(i) = f;
        for(int k=0; k<H; k++) cin >> S.at(i).at(k);
    }


    int answer = -1001001001,now = 0;
    vector<string> G = S.at(0);
    vector<string> best;
    if(H*W <= 18){
        auto dfs = [&](auto dfs,int x,int y) -> void {
            if(y == W) y = 0,x++;
            if(x == H){
                now = 0;
                for(int i=0; i<N; i++){
                    int ng = 0;
                    for(int k=0; k<H; k++) for(int l=0; l<W; l++) if(S.at(i).at(k).at(l) != G.at(k).at(l)) ng++;
                    if(ng <= F.at(i)) now += (i<U?1:-1);
                }
                if(answer < now) best = G;
                answer = max(answer,now);

                return;
            }
            G.at(x).at(y) = '.';
            dfs(dfs,x,y+1);
            G.at(x).at(y) = '#';
            dfs(dfs,x,y+1);
        };
        dfs(dfs,0,0);
        cout << answer << "\n";
        for(auto &g : best) cout << g << "\n";
        return 0;
    }
    answer = 0;
    {
        vector<string> zero(H,string(W,'.'));
        while(true){
            for(auto &h : zero) for(auto &w : h) w = mt()%2?'#':'.';
            bool ok = true;
            for(int i=0; i<N; i++){
                int ng = 0;
                for(int k=0; k<H; k++) for(int l=0; l<W; l++) if(S.at(i).at(k).at(l) != zero.at(k).at(l)) ng++;
                if(ng <= F.at(i)) ok = false;
            }
            if(ok){best = zero; break;}
        }
    }
    now = 1;
    vector<int> NG(N);
    for(int i=1; i<N; i++){
        for(int k=0; k<H; k++) for(int l=0; l<W; l++) if(S.at(i).at(k).at(l) != G.at(k).at(l)) NG.at(i)++;
        if(NG.at(i) <= F.at(i)) now += (i<U?1:-1);
    }
    auto update = [&]() -> void {if(answer < now) answer = now,best = G;};
    auto change = [&](int x,int y,char c) -> void {
        for(int i=0; i<N; i++){
            if(NG.at(i) <= F.at(i)) now -= (i<U?1:-1);
            if(S.at(i).at(x).at(y) != G.at(x).at(y)) NG.at(i)--;
        }
        G.at(x).at(y) = c;
        for(int i=0; i<N; i++){
            if(S.at(i).at(x).at(y) != G.at(x).at(y)) NG.at(i)++;
            if(NG.at(i) <= F.at(i)) now += (i<U?1:-1);
        }
    };
    for(int i=0; i<U; i++){
        if(i) for(int k=0; k<H; k++) for(int l=0; l<W; l++) change(k,l,S.at(i).at(k).at(l));
        update();
        for(int k=0; k<H; k++) for(int l=0; l<W; l++){
            change(k,l,S.at(i).at(k).at(l)^'#'^'.');
            update();
            change(k,l,S.at(i).at(k).at(l));
        }    
    }

    cout << answer << "\n";
    for(auto &g : best) cout << g << "\n";
}
0