結果

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

テストケース

テストケース表示
入力 結果 実行時間
使用メモリ
0sample1.txt AC 3 ms
1532 KB
0sample2.txt AC 4 ms
1524 KB
0sample3.txt AC 3 ms
1528 KB
1simple0.txt AC 3 ms
1520 KB
1simple1.txt AC 3 ms
1516 KB
1simple2.txt AC 4 ms
1512 KB
1simple3.txt AC 3 ms
1532 KB
1simple4.txt AC 4 ms
1528 KB
1simple5.txt AC 3 ms
1524 KB
1simple6.txt AC 3 ms
1528 KB
1simple7.txt AC 4 ms
1532 KB
1simple8.txt AC 4 ms
1532 KB
1simple9.txt AC 4 ms
1524 KB
1simple10.txt AC 3 ms
1532 KB
1simple11.txt AC 4 ms
1528 KB
2random1.txt AC 6 ms
1560 KB
2random2.txt AC 5 ms
1552 KB
2random3.txt AC 5 ms
1548 KB
2random4.txt AC 4 ms
1548 KB
2random5.txt AC 4 ms
1548 KB
2random6.txt AC 5 ms
1548 KB
5extreme0.txt AC 169 ms
1680 KB
5extreme1.txt AC 134 ms
1668 KB
5extreme2.txt AC 123 ms
1668 KB
5extreme3.txt AC 51 ms
1664 KB
5extreme4.txt AC 21 ms
1616 KB
5extreme5.txt AC 19 ms
1564 KB
5extreme6.txt AC 19 ms
1580 KB
5extreme7.txt AC 21 ms
1616 KB
5extreme8.txt AC 41 ms
1644 KB
5extreme9.txt AC 19 ms
1564 KB
6random1.txt AC 26 ms
1620 KB
6random2.txt AC 5 ms
1584 KB
6random3.txt AC 33 ms
1636 KB
6random4.txt AC 37 ms
1636 KB
6random5.txt AC 6 ms
1576 KB
6random6.txt AC 32 ms
1616 KB
6random7.txt AC 6 ms
1572 KB
6random8.txt AC 31 ms
1636 KB
6random9.txt AC 6 ms
1560 KB
6random10.txt AC 24 ms
1612 KB
6random11.txt AC 4 ms
1580 KB
6random12.txt AC 21 ms
1604 KB
6random13.txt AC 32 ms
1624 KB
6random14.txt AC 10 ms
1568 KB
6random15.txt AC 7 ms
1568 KB
6random16.txt AC 7 ms
1560 KB
6random17.txt AC 5 ms
1560 KB
6random18.txt AC 32 ms
1620 KB
6random19.txt AC 6 ms
1584 KB
6random20.txt AC 34 ms
1632 KB
gen_case1.txt AC 5 ms
1580 KB
gen_case2.txt AC 16 ms
1584 KB
gen_case3.txt AC 6 ms
1568 KB
gen_case4.txt AC 32 ms
1636 KB
gen_case5.txt AC 12 ms
1564 KB
gen_case6.txt AC 25 ms
1604 KB
gen_case7.txt AC 5 ms
1580 KB
gen_case8.txt AC 38 ms
1632 KB
gen_case9.txt AC 10 ms
1572 KB
gen_case10.txt AC 16 ms
1584 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