結果

問題 No.459 C-VS for yukicoder
ユーザー koyumeishi
提出日時 2016-12-10 01:40:24
言語 C++14
(gcc 7.2.0)
結果
AC  
実行時間 162 ms
コード長 6,738 Byte
コンパイル時間 3,931 ms
使用メモリ 17,316 KB
最終ジャッジ日時 2018-03-14 19:35:26

テストケース

テストケース表示
入力 結果 実行時間
使用メモリ
0sample1.txt AC 2 ms
1,584 KB
0sample2.txt AC 2 ms
1,576 KB
0sample3.txt AC 2 ms
1,580 KB
1simple0.txt AC 2 ms
1,584 KB
1simple1.txt AC 2 ms
1,584 KB
1simple2.txt AC 2 ms
1,588 KB
1simple3.txt AC 2 ms
1,588 KB
1simple4.txt AC 2 ms
1,584 KB
1simple5.txt AC 2 ms
1,584 KB
1simple6.txt AC 2 ms
1,580 KB
1simple7.txt AC 2 ms
1,584 KB
1simple8.txt AC 3 ms
1,584 KB
1simple9.txt AC 2 ms
1,580 KB
1simple10.txt AC 2 ms
1,588 KB
1simple11.txt AC 2 ms
1,592 KB
2random1.txt AC 5 ms
1,900 KB
2random2.txt AC 5 ms
1,816 KB
2random3.txt AC 3 ms
1,648 KB
2random4.txt AC 3 ms
1,644 KB
2random5.txt AC 3 ms
1,640 KB
2random6.txt AC 3 ms
1,640 KB
5extreme0.txt AC 162 ms
17,316 KB
5extreme1.txt AC 136 ms
16,260 KB
5extreme2.txt AC 140 ms
16,244 KB
5extreme3.txt AC 53 ms
7,160 KB
5extreme4.txt AC 21 ms
3,832 KB
5extreme5.txt AC 22 ms
3,404 KB
5extreme6.txt AC 20 ms
3,144 KB
5extreme7.txt AC 21 ms
3,816 KB
5extreme8.txt AC 47 ms
6,608 KB
5extreme9.txt AC 20 ms
3,408 KB
6random1.txt AC 28 ms
4,064 KB
6random2.txt AC 3 ms
2,088 KB
6random3.txt AC 36 ms
4,728 KB
6random4.txt AC 40 ms
5,352 KB
6random5.txt AC 5 ms
2,084 KB
6random6.txt AC 37 ms
5,144 KB
6random7.txt AC 5 ms
1,896 KB
6random8.txt AC 35 ms
4,700 KB
6random9.txt AC 5 ms
1,824 KB
6random10.txt AC 26 ms
3,820 KB
6random11.txt AC 4 ms
1,864 KB
6random12.txt AC 24 ms
3,668 KB
6random13.txt AC 35 ms
4,940 KB
6random14.txt AC 10 ms
2,088 KB
6random15.txt AC 8 ms
2,088 KB
6random16.txt AC 7 ms
1,820 KB
6random17.txt AC 6 ms
1,820 KB
6random18.txt AC 37 ms
4,988 KB
6random19.txt AC 5 ms
1,900 KB
6random20.txt AC 34 ms
4,540 KB
gen_case1.txt AC 4 ms
2,084 KB
gen_case2.txt AC 17 ms
2,876 KB
gen_case3.txt AC 6 ms
1,820 KB
gen_case4.txt AC 37 ms
4,764 KB
gen_case5.txt AC 12 ms
2,436 KB
gen_case6.txt AC 25 ms
3,756 KB
gen_case7.txt AC 4 ms
2,084 KB
gen_case8.txt AC 41 ms
5,328 KB
gen_case9.txt AC 9 ms
2,232 KB
gen_case10.txt AC 16 ms
2,872 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