fork download
copy 
  1.  
  2. #include <bits/stdc++.h>
  3. using namespace std;
  4.  
  5. struct Dinic {
  6.     struct Edge {
  7.         int to, rev, cap;
  8.     };
  9.  
  10.     int n;
  11.     vector<vector<Edge>> g;
  12.     vector<int> level, ptr;
  13.  
  14.     Dinic(int n) : n(n), g(n), level(n), ptr(n) {}
  15.  
  16.     void addEdge(int u, int v, int cap) {
  17.         Edge a{v, (int)g[v].size(), cap};
  18.         Edge b{u, (int)g[u].size(), 0};
  19.  
  20.         g[u].push_back(a);
  21.         g[v].push_back(b);
  22.     }
  23.  
  24.     bool bfs(int s, int t) {
  25.         fill(level.begin(), level.end(), -1);
  26.  
  27.         queue<int> q;
  28.         q.push(s);
  29.         level[s] = 0;
  30.  
  31.         while (!q.empty()) {
  32.             int v = q.front();
  33.             q.pop();
  34.  
  35.             for (auto &e : g[v]) {
  36.                 if (e.cap > 0 && level[e.to] == -1) {
  37.                     level[e.to] = level[v] + 1;
  38.                     q.push(e.to);
  39.                 }
  40.             }
  41.         }
  42.  
  43.         return level[t] != -1;
  44.     }
  45.  
  46.     int dfs(int v, int t, int pushed) {
  47.         if (pushed == 0) return 0;
  48.         if (v == t) return pushed;
  49.  
  50.         for (int &cid = ptr[v]; cid < (int)g[v].size(); cid++) {
  51.             Edge &e = g[v][cid];
  52.  
  53.             if (e.cap <= 0 || level[e.to] != level[v] + 1)
  54.                 continue;
  55.  
  56.             int tr = dfs(e.to, t, min(pushed, e.cap));
  57.  
  58.             if (tr == 0) continue;
  59.  
  60.             e.cap -= tr;
  61.             g[e.to][e.rev].cap += tr;
  62.  
  63.             return tr;
  64.         }
  65.  
  66.         return 0;
  67.     }
  68.  
  69.     int maxflow(int s, int t, int limit) {
  70.         int flow = 0;
  71.  
  72.         while (flow < limit && bfs(s, t)) {
  73.             fill(ptr.begin(), ptr.end(), 0);
  74.  
  75.             while (flow < limit) {
  76.                 int pushed = dfs(s, t, limit - flow);
  77.  
  78.                 if (pushed == 0) break;
  79.  
  80.                 flow += pushed;
  81.             }
  82.         }
  83.  
  84.         return flow;
  85.     }
  86. };
  87.  
  88. bool check(int i, int j,
  89.            const vector<int> &r,
  90.            const vector<int> &c,
  91.            int n, int m) {
  92.  
  93.     int need = 0;
  94.  
  95.     for (int x = i; x < n; x++)
  96.         need += r[x];
  97.  
  98.     int S = 0;
  99.  
  100.     int rowBase = 1;
  101.     int colBase = rowBase + (n - i);
  102.     int T = colBase + m;
  103.  
  104.     Dinic dinic(T + 1);
  105.  
  106.     for (int x = i; x < n; x++) {
  107.         dinic.addEdge(S, rowBase + x - i, r[x]);
  108.     }
  109.  
  110.     for (int y = 0; y < m; y++) {
  111.         dinic.addEdge(colBase + y, T, c[y]);
  112.     }
  113.  
  114.     for (int x = i; x < n; x++) {
  115.  
  116.         int firstCol = (x == i ? j + 1 : 0);
  117.  
  118.         for (int y = firstCol; y < m; y++) {
  119.  
  120.             if (r[x] == 0 || c[y] == 0)
  121.                 continue;
  122.  
  123.             dinic.addEdge(
  124.                 rowBase + x - i,
  125.                 colBase + y,
  126.                 1
  127.             );
  128.         }
  129.     }
  130.  
  131.     return dinic.maxflow(S, T, need) == need;
  132. }
  133.  
  134. int main() {
  135.     ios::sync_with_stdio(false);
  136.     cin.tie(nullptr);
  137.  
  138.     int n, m;
  139.     cin >> n >> m;
  140.  
  141.     vector<int> r(n), c(m);
  142.  
  143.     int sumR = 0, sumC = 0;
  144.  
  145.     for (int &x : r) {
  146.         cin >> x;
  147.         sumR += x;
  148.     }
  149.  
  150.     for (int &x : c) {
  151.         cin >> x;
  152.         sumC += x;
  153.     }
  154.  
  155.     if (sumR != sumC) {
  156.         cout << -1;
  157.         return 0;
  158.     }
  159.  
  160.     for (int x : r)
  161.         if (x < 0 || x > m) {
  162.             cout << -1;
  163.             return 0;
  164.         }
  165.  
  166.     for (int x : c)
  167.         if (x < 0 || x > n) {
  168.             cout << -1;
  169.             return 0;
  170.         }
  171.  
  172.     vector<string> ans(n, string(m, '0'));
  173.  
  174.     for (int i = 0; i < n; i++) {
  175.         for (int j = 0; j < m; j++) {
  176.  
  177.             if (check(i, j, r, c, n, m)) {
  178.                 ans[i][j] = '0';
  179.             }
  180.             else {
  181.                 if (r[i] == 0 || c[j] == 0) {
  182.                     cout << -1;
  183.                     return 0;
  184.                 }
  185.  
  186.                 ans[i][j] = '1';
  187.  
  188.                 r[i]--;
  189.                 c[j]--;
  190.             }
  191.         }
  192.     }
  193.  
  194.     for (int x : r) {
  195.         if (x != 0) {
  196.             cout << -1;
  197.             return 0;
  198.         }
  199.     }
  200.  
  201.     for (int x : c) {
  202.         if (x != 0) {
  203.             cout << -1;
  204.             return 0;
  205.         }
  206.     }
  207.  
  208.     for (auto &s : ans)
  209.         cout << s << '\n';
  210.  
  211.     return 0;
  212. }
  213.  
Success #stdin #stdout 0s 5320KB
comments (?)
stdin
copy 
3 3
2 1 2
1 2 2
stdout
copy 
011
001
110
https://ideone.com/DhI5hd
language:
C++14 (gcc 8.3)
created:
2 hours ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!