Submission #49672663

---

Source Code Expand

#include <bits/stdc++.h>
#include <atcoder/maxflow>
using namespace std;
#define rep(i,a,n) for (int i=a;i<(int)(n);i++)
int read(){int r;scanf("%d",&r);return r;}

int n,m;
const int INF=100*100000;
char s[100][100010];
int ans = INF;
vector<pair<int,vector<int> > > right_[10]; // {tick, vector<int> left}
int solve(const vector<pair<int,vector<int> > >&right){
  int l = 0;
  int r = INF+1;
  auto check=[&](int t){
    int S = 0;
    int T = 1;
    int loff = 2;
    int roff = 2+n;
    auto g = atcoder::mf_graph<int>(2+n+right.size());
    rep(i,0,n) g.add_edge(S,loff+i,1); // S -> string
    rep(j,0,size(right)) {
      auto &[tick,lefts] = right[j];
      g.add_edge(roff+j,T,t/m+int((t%m) >= tick));
      for(auto left:lefts) g.add_edge(loff+left, roff+j, n);
    }
    return g.flow(S,T,n) == n;
  };
  while(r-l > 1){
    int mid = (l+r)/2;
    if(check(mid)){
      r = mid;
    }else{
      l = mid;
    }
  }
  return check(l)?l:r;
}

int main(){
  n=read(); // <= 100
  m=read();
  rep(i,0,n) scanf("%s",s[i]);

  vector count(10,vector<int>(n,0)); // count[char][row]
  rep(i,0,n) rep(j,0,m) {
    auto res = ++count[s[i][j]-'0'][i];
    if(res > n+1) s[i][j] = '9'+1; // 无效化, 让左侧最多配前n个 ！！！
  }

  rep(j,0,m) {
    vector pos(11,vector<int>()); // 多一维无效化 !!!
    rep(i,0,n) pos[s[i][j]-'0'].push_back(i);
    rep(c,0,10) if(pos[c].size()) right_[c].push_back({j,pos[c]});
  }

  rep(v,0,9+1) {
    int sum = 0;
    rep(i,0,n) sum += bool(count[v][i]);
    if(sum == n) ans = min(ans, solve(right_[v]));
  }
  printf("%d\n",ans==INF?-1:ans);
  return 0;
}

Submission Info

Compile Error

Main.cpp: In function ‘int read()’:
Main.cpp:5:23: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
    5 | int read(){int r;scanf("%d",&r);return r;}
      |                  ~~~~~^~~~~~~~~
Main.cpp: In function ‘int main()’:
Main.cpp:43:19: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
   43 |   rep(i,0,n) scanf("%s",s[i]);
      |              ~~~~~^~~~~~~~~~~

Judge Result