結果

問題 No.3410 Happiest Art
コンテスト
ユーザー Kude
提出日時 2025-12-17 00:38:34
言語 C++23
(gcc 13.3.0 + boost 1.89.0)
結果
AC  
実行時間 658 ms / 4,000 ms
コード長 2,445 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 3,565 ms
コンパイル使用メモリ 308,612 KB
実行使用メモリ 47,292 KB
最終ジャッジ日時 2025-12-17 00:38:44
合計ジャッジ時間 8,590 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 44
権限があれば一括ダウンロードができます
コンパイルメッセージ
main.cpp: In function ‘int main()’:
main.cpp:49:44: warning: narrowing conversion of ‘z’ from ‘int’ to ‘signed char’ [-Wnarrowing]
   49 |     auto [it, inserted] = d.emplace(now, S{z, -1, -1, add});
      |                                            ^
main.cpp:53:59: warning: narrowing conversion of ‘z’ from ‘int’ to ‘signed char’ [-Wnarrowing]
   53 |         auto [it, inserted] = d.emplace(now ^ hs[i][j], S{z, i, j, add});
      |                                                           ^
main.cpp:53:62: warning: narrowing conversion of ‘i’ from ‘int’ to ‘signed char’ [-Wnarrowing]
   53 |         auto [it, inserted] = d.emplace(now ^ hs[i][j], S{z, i, j, add});
      |                                                              ^
main.cpp:53:65: warning: narrowing conversion of ‘j’ from ‘int’ to ‘signed char’ [-Wnarrowing]
   53 |         auto [it, inserted] = d.emplace(now ^ hs[i][j], S{z, i, j, add});
      |                                                                 ^

ソースコード

diff #
raw source code 

#include<bits/stdc++.h>
namespace {
#pragma GCC diagnostic ignored "-Wunused-function"
#include<atcoder/all>
#pragma GCC diagnostic warning "-Wunused-function"
using namespace std;
using namespace atcoder;
#define rep(i,n) for(int i = 0; i < (int)(n); i++)
#define rrep(i,n) for(int i = (int)(n) - 1; i >= 0; i--)
#define all(x) begin(x), end(x)
#define rall(x) rbegin(x), rend(x)
template<class T> bool chmax(T& a, const T& b) { if (a < b) { a = b; return true; } else return false; }
template<class T> bool chmin(T& a, const T& b) { if (b < a) { a = b; return true; } else return false; }
using ll = long long;
using P = pair<int,int>;
using VI = vector<int>;
using VVI = vector<VI>;
using VL = vector<ll>;
using VVL = vector<VL>;


std::mt19937 RNG(std::chrono::system_clock::now().time_since_epoch().count());
unsigned long long RULL() {
  return std::uniform_int_distribution<unsigned long long>()(RNG);
}

using ull = unsigned long long;
ull hs[100][100];

} int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  rep(i, 100) rep(j, 100) hs[i][j] = RULL();
  int n, u, h, w;
  cin >> n >> u >> h >> w;
  using A = array<array<char, 100>, 100>;
  static A s[100]{};
  static int f[100]{};
  struct S {
    signed char z, i, j, val;
  };
  unordered_map<ull, S> d;
  rep(z, n) {
    cin >> f[z];
    rep(i, h) rep(j, w) cin >> s[z][i][j];
    signed char add = z < u ? 1 : -1;
    ull now = 0;
    rep(i, h) rep(j, w) now ^= (s[z][i][j] == '#') * hs[i][j];
    auto [it, inserted] = d.emplace(now, S{z, -1, -1, add});
    if (!inserted) it->second.val += add;
    if (f[z] == 1) {
      rep(i, h) rep(j, w) {
        auto [it, inserted] = d.emplace(now ^ hs[i][j], S{z, i, j, add});
        if (!inserted) it->second.val += add;
      }
    }
  }
  int mx = -10000;
  A ans{};
  A g{};
  auto dfs = [&](auto&& self, int i, int j, ull now) -> bool {
    if (j == w) j = 0, i++;
    if (i == h) {
      if (d.contains(now)) return false;
      mx = 0;
      return true;
    }
    g[i][j] = '.';
    if (self(self, i, j + 1, now)) return true;
    g[i][j] = '#';
    return self(self, i, j + 1, now ^ hs[i][j]);
  };
  dfs(dfs, 0, 0, 0);
  S smx{-1, -1, -1, -1};
  for (auto [_, v] : d) {
    if (chmax<int>(mx, v.val)) smx = v;
  }
  if (smx.z != -1) {
    auto [z, i, j, val] = smx;
    ans = s[z];
    if (i != -1) ans[i][j] ^= '.' ^ '#';
  }
  cout << mx << '\n';
  rep(i, h) {
    rep(j, w) cout << ans[i][j];
    cout << '\n';
  }
}
0