結果

問題 No.459 C-VS for yukicoder
ユーザー koyumeishi
提出日時 2016-12-10 01:40:24
言語 C++14
(gcc 7.2.0)
結果
AC  
実行時間 137 ms
コード長 6738 Byte
コンパイル時間 2152 ms
使用メモリ 1688 KB

テストケース

テストケース表示
入力 結果 実行時間
使用メモリ
0sample1.txt AC 5 ms
1532 KB
0sample2.txt AC 4 ms
1532 KB
0sample3.txt AC 4 ms
1536 KB
1simple0.txt AC 4 ms
1520 KB
1simple1.txt AC 4 ms
1512 KB
1simple2.txt AC 4 ms
1516 KB
1simple3.txt AC 4 ms
1532 KB
1simple4.txt AC 3 ms
1532 KB
1simple5.txt AC 4 ms
1528 KB
1simple6.txt AC 3 ms
1532 KB
1simple7.txt AC 4 ms
1532 KB
1simple8.txt AC 3 ms
1532 KB
1simple9.txt AC 4 ms
1528 KB
1simple10.txt AC 4 ms
1532 KB
1simple11.txt AC 4 ms
1536 KB
2random1.txt AC 7 ms
1556 KB
2random2.txt AC 6 ms
1548 KB
2random3.txt AC 4 ms
1548 KB
2random4.txt AC 4 ms
1544 KB
2random5.txt AC 4 ms
1548 KB
2random6.txt AC 4 ms
1544 KB
5extreme0.txt AC 137 ms
1688 KB
5extreme1.txt AC 129 ms
1668 KB
5extreme2.txt AC 125 ms
1664 KB
5extreme3.txt AC 52 ms
1664 KB
5extreme4.txt AC 25 ms
1620 KB
5extreme5.txt AC 22 ms
1572 KB
5extreme6.txt AC 22 ms
1580 KB
5extreme7.txt AC 25 ms
1612 KB
5extreme8.txt AC 49 ms
1652 KB
5extreme9.txt AC 21 ms
1572 KB
6random1.txt AC 36 ms
1612 KB
6random2.txt AC 6 ms
1580 KB
6random3.txt AC 39 ms
1632 KB
6random4.txt AC 39 ms
1632 KB
6random5.txt AC 7 ms
1580 KB
6random6.txt AC 38 ms
1616 KB
6random7.txt AC 7 ms
1572 KB
6random8.txt AC 34 ms
1628 KB
6random9.txt AC 7 ms
1556 KB
6random10.txt AC 28 ms
1612 KB
6random11.txt AC 6 ms
1576 KB
6random12.txt AC 24 ms
1608 KB
6random13.txt AC 35 ms
1616 KB
6random14.txt AC 11 ms
1560 KB
6random15.txt AC 11 ms
1560 KB
6random16.txt AC 9 ms
1560 KB
6random17.txt AC 7 ms
1560 KB
6random18.txt AC 37 ms
1624 KB
6random19.txt AC 5 ms
1576 KB
6random20.txt AC 32 ms
1628 KB
gen_case1.txt AC 6 ms
1580 KB
gen_case2.txt AC 17 ms
1580 KB
gen_case3.txt AC 8 ms
1564 KB
gen_case4.txt AC 35 ms
1632 KB
gen_case5.txt AC 13 ms
1556 KB
gen_case6.txt AC 25 ms
1600 KB
gen_case7.txt AC 6 ms
1576 KB
gen_case8.txt AC 37 ms
1624 KB
gen_case9.txt AC 11 ms
1572 KB
gen_case10.txt AC 18 ms
1580 KB
テストケース一括ダウンロード

ソースコード

diff #
#include <iostream>
#include <vector>
#include <cstdio>
#include <sstream>
#include <map>
#include <string>
#include <algorithm>
#include <queue>
#include <cmath>
#include <functional>
#include <set>
#include <ctime>
#include <random>
#include <chrono>
#include <cassert>
#include <tuple>
#include <utility>
using namespace std;

namespace {
  using Integer = long long; //__int128;
  template<class T, class S> istream& operator >> (istream& is, pair<T,S>& p){return is >> p.first >> p.second;}
  template<class T> istream& operator >> (istream& is, vector<T>& vec){for(T& val: vec) is >> val; return is;}
  template<class T> istream& operator ,  (istream& is, T& val){ return is >> val;}
  template<class T, class S> ostream& operator << (ostream& os, const pair<T,S>& p){return os << p.first << " " << p.second;}
  template<class T> ostream& operator << (ostream& os, const vector<T>& vec){for(size_t i=0; i<vec.size(); i++) os << vec[i] << (i==vec.size()-1?"":" "); return os;}
  template<class T> ostream& operator ,  (ostream& os, const T& val){ return os << " " << val;}

  template<class H> void print(const H& head){ cout << head; }
  template<class H, class ... T> void print(const H& head, const T& ... tail){ cout << head << " "; print(tail...); }
  template<class ... T> void println(const T& ... values){ print(values...); cout << endl; }

  template<class H> void eprint(const H& head){ cerr << head; }
  template<class H, class ... T> void eprint(const H& head, const T& ... tail){ cerr << head << " "; eprint(tail...); }
  template<class ... T> void eprintln(const T& ... values){ eprint(values...); cerr << endl; }

  class range{ Integer start_, end_, step_; public: struct range_iterator{ Integer val, step_; range_iterator(Integer v, Integer step) : val(v), step_(step) {} Integer operator * (){return val;} void operator ++ (){val += step_;} bool operator != (range_iterator& x){return step_ > 0 ? val < x.val : val > x.val;} }; range(Integer len) : start_(0), end_(len), step_(1) {} range(Integer start, Integer end) : start_(start), end_(end), step_(1) {} range(Integer start, Integer end, Integer step) : start_(start), end_(end), step_(step) {} range_iterator begin(){ return range_iterator(start_, step_); } range_iterator   end(){ return range_iterator(  end_, step_); } };

  inline string operator "" _s (const char* str, size_t size){ return move(string(str)); }
  constexpr Integer my_pow(Integer x, Integer k, Integer z=1){return k==0 ? z : k==1 ? z*x : (k&1) ? my_pow(x*x,k>>1,z*x) : my_pow(x*x,k>>1,z);}
  constexpr Integer my_pow_mod(Integer x, Integer k, Integer M, Integer z=1){return k==0 ? z%M : k==1 ? z*x%M : (k&1) ? my_pow_mod(x*x%M,k>>1,M,z*x%M) : my_pow_mod(x*x%M,k>>1,M,z);}
  constexpr unsigned long long operator "" _ten (unsigned long long value){ return my_pow(10,value); }

  inline int k_bit(Integer x, int k){return (x>>k)&1;} //0-indexed

  mt19937 mt(chrono::duration_cast<chrono::nanoseconds>(chrono::steady_clock::now().time_since_epoch()).count());

  template<class T> string join(const vector<T>& v, const string& sep){ stringstream ss; for(size_t i=0; i<v.size(); i++){ if(i>0) ss << sep; ss << v[i]; } return ss.str(); }

  inline string operator * (string s, int k){ string ret; while(k){ if(k&1) ret += s; s += s; k >>= 1; } return ret; }
}
constexpr long long mod = 9_ten + 7;



typedef struct{
  int to;
  int cap;
  int rev;
}edge;

// node v : distance from s => level[v]
void bfs(vector<vector<edge> > &G, vector<int> &level, int s){
  fill(level.begin(), level.end(), -1);
  queue<int> q;
  q.push(s);
  level[s] = 0;
  while(!q.empty()){
    int e=q.front(); q.pop();
    for(int i=0; i<G[e].size(); i++){
      if(G[e][i].cap > 0 && level[G[e][i].to] < 0){
        level[G[e][i].to] = level[e] + 1;
        q.push(G[e][i].to);
      }
    }
  }
}

int dfs(vector<vector<edge> > &G, vector<int> &level, vector<bool> &used, vector<int> &iter, int s, int f,  int t){
  if(s==t) return f;
  else{
    //iter[e] : done searching from v[0] to v[ iter[e]-1 ]
    for(int &i=iter[s]; i<G[s].size(); i++){
      //distance from s to v[e][i].to must be longer than dist from s to v
      if(G[s][i].cap > 0 && level[s] < level[ G[s][i].to ]){
        int d = dfs(G, level, used, iter, G[s][i].to, min(f, G[s][i].cap), t);
        if(d>0){
          G[s][i].cap -= d;
          G[ G[s][i].to ][ G[s][i].rev ].cap += d;
          return d;
        }
      }
    }
    return 0;
  }
}

int dinic_maxflow(vector<vector<edge> > &G, int s, int t){
  const int INF = 100000000;
  int flow=0;
  while(true){
    vector<int> level(G.size(), -1);
    vector<int> iter(G.size(), 0);
    vector<bool> used(G.size(), false);
    bfs(G, level, s);
    if(level[t] < 0) return flow; //unable to achieve to t
    while(true){
      int f = dfs(G, level, used, iter, s, INF, t);
      if(f==0) break;
      else flow += f;
    }
  }
}

void add_edge(vector<vector<edge> > &G, int from, int to, int cap){
  G[from].push_back((edge){to, cap, (int)G[to].size()});
  G[to].push_back((edge){from, 0, (int)G[from].size() - 1});
}


int main(){
  int h,w,n;
  cin >> h,w,n;
  vector<string> ss(h);
  cin >> ss;

  vector<int> cnt(w, 0);
  for(auto i : range(h) ){
    for(auto j : range(w) ){
      cnt[j] += ss[i][j] == '#';
    }
  }

  int sum = accumulate(cnt.begin(), cnt.end(), 0);

  vector<int> c(n);
  cin >> c;

  vector<vector<edge>> G(w + 2*n + 4);
  int s = w+2*n + 0;
  int t = w+2*n + 1;
  int S = w+2*n + 2;
  int T = w+2*n + 3;

  add_edge(G, S, s, sum);
  add_edge(G, t, T, sum);
    
  for(int i : range(n)){
    int u = w+i;
    int v = w+n+i;

    add_edge(G, s, u, 9);

    add_edge(G, u, v, 9-1);
    
    add_edge(G, u, T,  1);
    add_edge(G, S, v, 1);

    for(int j=c[i]; j<c[i]+3 && j<w; j++){
      add_edge(G, v, j, 3);
    }
  }
  for(int i=0; i<w; i++){
    add_edge(G, i, t, cnt[i]);
  }

  int f = dinic_maxflow(G, S,T);
  eprintln(f);
  assert(f-n == accumulate(cnt.begin(), cnt.end(), 0));
  // f = dinic_maxflow(G, s,t);
  // eprintln(f);

  vector<vector<int>> kuso(n, vector<int>(3, 0));
  for(auto i : range(w+n, w+n+n)){
    for(auto e : G[i]){
      if( e.to < w ){
        int d = e.to - c[i-w-n];
        kuso[i-w-n][d] = 3-e.cap;
      }
    }
  }


  vector<vector<string>> p(n, vector<string>(3, string(3, '.')));
  for(int i : range(n)){
    for(int d : range(3)){
      for(int k : range(kuso[i][d])){
        p[i][k][d] = '#';
      }
    }
  }

  vector<string> aho = {"...", "..." , "..."};

  vector<int> unko(w, 0);
  for(auto i : range(h) ){
    for(auto j : range(w) ){
      unko[j] += ss[i][j] == '#';
    }
  }

  //assert(unko == cnt);

  for(auto i : range(n) ){
    println(join(p[i], "\n"));
    assert(p[i] != aho);
  }

  return 0;
}
0