結果

問題 No.3410 Happiest Art
コンテスト
ユーザー kazuppa
提出日時 2025-12-17 00:17:57
言語 C++17
(gcc 13.3.0 + boost 1.89.0)
結果
AC  
実行時間 1,550 ms / 4,000 ms
コード長 2,436 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 2,520 ms
コンパイル使用メモリ 222,152 KB
実行使用メモリ 82,452 KB
最終ジャッジ日時 2025-12-17 00:18:14
合計ジャッジ時間 10,058 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 44
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

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

random_device seed_gen;
mt19937_64 engine(seed_gen());
ll randint(ll l,ll r){return l+engine()%(r-l);}

vector<int> arttobit(string s){
  vector<int> e;
  for(auto i:s)e.emplace_back(i=='#');
  return e;
}
string bittoart(vector<int> a){
  string s="";
  for(auto i:a)s+=(i?'#':'.');
  return s;
}
int hw;
ll m,b;
vector<ll> bpow;
ll bittohash(vector<int> a){
  ll t=0;
  for(int i=0;i<hw;i++){
    t+=a[i]*bpow[i];
    t%=m;
  }
  return t;
}

void solve(){
  m=randint(1e17+3,1e18+4),b=randint(2,6);
  int n,u;cin>>n>>u;
  int h,w;cin>>h>>w;
  hw=h*w;
  bpow.resize(hw+1);bpow[0]=1;
  for(int i=0;i<hw+1;i++)bpow[i]=bpow[i-1]*b%m;
  vector<pair<ll,ll>> g;
  vector<string> t(n);
  map<ll,pair<int,int>> mh;
  for(int x=0;x<n;x++){
    int f;cin>>f;
    int e;
    if(x<u)e=1;
    else e=-1;
    string s="";
    for(int i=0;i<h;i++)
      for(int j=0;j<w;j++){
        char c;cin>>c;
        s+=c;
      }
    t[x]=s;
    vector<int> p=arttobit(s);
    ll u=bittohash(p);
    g.emplace_back(u,e);
    mh[u]={x,-1};
    if(f){
      for(int i=0;i<hw;i++){
        ll v=u;
        if(!p[i])v+=bpow[i];
        else v-=bpow[i];
        v%=m;
        if(v<0)v+=m;
        g.emplace_back(v,e);
        mh[v]={x,i};
      }
    }
  }
  sort(g.begin(),g.end());
  for(int i=0;i<(n+1)*hw+1;i++){
    if(hw<=30&&i>=(1<<hw))break;
    string s="";ll u=0;
    for(int j=0;j<min(31,hw);j++)
      if((i&(1<<j)))u+=bpow[j],u%=m;
    pair<ll,ll> e={u,0};
    int l=0,r=g.size();
    while(r-l>1){
      int m=(l+r)/2;
      if(g[m].first<=e.first)l=m;
      else r=m;
    }
    if(g[l].first!=e.first){
      string s="";
      for(int j=0;j<hw;j++){
        if(j<=30&&(i&(1<<j)))s+='#';
        else s+='.';
      }
      t.emplace_back(s);
      g.emplace_back(e);
      mh[u]={n,-1};
      break;
    }
  }
  int l=0,s=-1.1e9;
  for(int i=0;i<g.size();i++){
    int r=i,ns=0;
    while(r<g.size()&&g[r].first==g[i].first)ns+=g[r].second,r++;
    if(ns>s)l=i,s=ns;
    i=r-1;
  }
  cout<<s<<endl;
  vector<string> e(h);pair<int,int> o=mh[g[l].first];
  for(int i=0;i<h;i++)
    for(int j=0;j<w;j++)
      if(o.second==i*w+j){
        if(t[o.first][i*w+j]=='#')e[i]+='.';
        else e[i]+='#';
      }
      else e[i]+=t[o.first][i*w+j];
  for(auto i:e)cout<<i<<endl;
}

int main(){
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  int t=1;//input(t);
  while(t--)solve();
}
0