QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#288856#7857. (-1,1)-Sumpleteucup-team896#TL 16ms29056kbC++143.3kb2023-12-23 13:55:002023-12-23 13:55:01

Judging History

你现在查看的是最新测评结果

  • [2023-12-23 13:55:01]
  • 评测
  • 测评结果:TL
  • 用时:16ms
  • 内存:29056kb
  • [2023-12-23 13:55:00]
  • 提交

answer

#include <bits/stdc++.h>
#ifdef dbg
#define D(...) fprintf(stderr, __VA_ARGS__)
#define DD(...) D("[Debug] "#__VA_ARGS__ " = "), \
              debug_helper::debug(__VA_ARGS__), D("\n")
#include "C:\Users\wsyear\Desktop\OI\templates\debug.hpp"
#else
#define D(...) ((void)0)
#define DD(...) ((void)0)
#endif
#define rep(i, j, k) for (int i = (j); i <= (k); ++i)
#define per(i, j, k) for (int i = (j); i >= (k); --i)
#define SZ(v) int((v).size())
#define ALL(v) (v).begin(),(v).end()
#define fi first
#define se second
using ll = long long;
using pii = std::pair<int, int>;
using pll = std::pair<ll, ll>;

template<class T> void chkmn(T &x, T y) { if (y < x) x = y; }
template<class T> void chkmx(T &x, T y) { if (y > x) x = y; }

using namespace std;

struct MF {
  static const int N = 10010;
  static const int M = 20000010;
  int s, t, head[N], to[M << 1], nxt[M << 1], flow[M << 1], cur[N], d[N], tot = 1;
  void init() {
    memset(head, 0, sizeof(head));
    tot = 1;
  }
  void addedge(int u, int v, int w) {
    to[++tot] = v, flow[tot] = w, nxt[tot] = head[u], head[u] = tot;
  }
  void add(int u, int v, int w) {
    addedge(u, v, w);
    addedge(v, u, 0);
  }
  bool bfs() {
    queue<int> q;
    memset(d, 0, sizeof(d));
    d[s] = 1, q.push(s);
    while (!q.empty()) {
      int u = q.front();
      q.pop(), cur[u] = head[u];
      for (int i = head[u]; i; i = nxt[i]) {
        int v = to[i], w = flow[i];
        if (w > 0 && !d[v])
          d[v] = d[u] + 1, q.push(v);
      }
    }
    return d[t];
  }
  int dfs(int u, int now) {
    if (u == t || !now) return now;
    int rest = now;
    for (int i = cur[u]; i && rest > 0; i = nxt[i]) {
      cur[u] = i;
      int v = to[i], w = flow[i];
      if (d[v] == d[u] + 1 && w > 0) {
        int cap = dfs(v, min(rest, w));
        if (cap) flow[i] -= cap, flow[i ^ 1] += cap, rest -= cap;
      }
    }
    return now - rest;
  }
  int mf() {
    int res = 0, cap;
    while (bfs()) while (cap = dfs(s, 1e9)) res += cap;
    return res;
  }
} g;

const int maxn = 4010;

int n, s, t, a[maxn], b[maxn], ans[maxn][maxn];
char str[maxn][maxn];

int main() {
  cin.tie(nullptr) -> ios::sync_with_stdio(false);
  cin >> n;
  rep (i, 1, n) cin >> (str[i] + 1);
  rep (i, 1, n) cin >> a[i];
  rep (i, 1, n) cin >> b[i];
  g.init(), s = g.s = 2 * n + 1, t = g.t = 2 * n + 2;
  rep (i, 1, n) {
    int s = 0;
    rep (j, 1, n) {
      if (str[i][j] == '-') s--;
    }
    a[i] -= s;
  }
  rep (i, 1, n) {
    int s = 0;
    rep (j, 1, n) {
      if (str[j][i] == '-') s--;
    }
    b[i] -= s;
  }
  rep (i, 1, n) if (a[i] > n) return cout << "No\n", 0;
  rep (i, 1, n) if (b[i] > n) return cout << "No\n", 0;
  rep (i, 1, n) g.add(s, i, a[i]), g.add(n + i, t, b[i]);
  rep (i, 1, n) rep (j, 1, n) g.add(i, n + j, 1);
  int s = 0;
  rep (i, 1, n) s += a[i];
  if (g.mf() != s) return cout << "No\n", 0;
  rep (i, 1, n) s -= b[i];
  if (s != 0) return cout << "No\n", 0;
  rep (i, 1, n) rep (j, 1, n) ans[i][j] = (str[i][j] == '-');
  rep (i, 1, n) {
    for (int x = g.head[i]; x; x = g.nxt[x]) {
      if (g.to[x] > n && g.to[x] <= 2 * n && g.flow[x] == 0) {
        ans[i][g.to[x] - n] ^= 1;
      }
    }
  }
  cout << "Yes\n";
  rep (i, 1, n) {
    rep (j, 1, n) cout << ans[i][j];
    cout << "\n";
  }
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 2ms
memory: 11644kb

input:

3
+-+
-++
+-+
1 1 1
1 -1 3

output:

Yes
111
001
001

result:

ok n=3

Test #2:

score: 0
Accepted
time: 2ms
memory: 11692kb

input:

3
---
-++
+++
-2 -1 0
-2 -1 0

output:

Yes
110
100
000

result:

ok n=3

Test #3:

score: 0
Accepted
time: 0ms
memory: 9724kb

input:

3
+-+
-++
++-
1 0 2
2 2 -1

output:

No

result:

ok n=3

Test #4:

score: 0
Accepted
time: 0ms
memory: 5608kb

input:

1
-
-1
1

output:

No

result:

ok n=1

Test #5:

score: 0
Accepted
time: 2ms
memory: 11684kb

input:

1
-
0
0

output:

Yes
0

result:

ok n=1

Test #6:

score: 0
Accepted
time: 2ms
memory: 11764kb

input:

20
+-------+-----+++-++
-+-++++----++-++-++-
-+++--+---+--+-++---
-+++-+--+----++---+-
+++-+-++++++-+-+---+
-++-----+----++++++-
+-++--+++++-++-+----
+-+----+---+-+++--+-
+++++-+++++----+--+-
------++++---+--++--
++++--------++++--+-
-+-+-++++-+-++-++--+
---+-++---+-++-++---
+-++++-++----+-+++--
+-+...

output:

Yes
10000011011111011011
01011111111001010110
01110011110110100000
01110101111110011101
11101010100010110001
10100000111101001001
01001011100111100111
01010001001101000111
00000100110000000111
11111100110001011001
00001111111111100111
10101000001011011100
11101110001011011100
01000010100001011100
01...

result:

ok n=20

Test #7:

score: 0
Accepted
time: 0ms
memory: 12080kb

input:

100
++++-+-+--++++++-+--+--++-+-+--+++++-+++---+-+-+-++-+-+++-------+-++--+-++--+--+++++-++-+---+--+--++
-++--++-+-++++-+---++-+-+-+-+-+-+-+-+--+-+--+--+++---+--+-----+-----+-++-++-+-++++++--+-+++-+++-++++
--+---++-++--++-+++-------+--+-++------+-----+--+----++++++++-+--+++++--++--+-+-+++---+--+++-+...

output:

Yes
1111010100111111010010100101011000001000111011010110101110000000101100101100100111110110100010010011
0110011010111101000110010101010101010101010010011100010010000010000010110110101111110010111011101111
0010001101100110111000111101101001111110111001001000011111111010011111001100101011100010011101...

result:

ok n=100

Test #8:

score: 0
Accepted
time: 16ms
memory: 29056kb

input:

500
--+-+-+-++-----+++--+-+++-+---+-+-------+++--++++++-+--++--+-+-++++-++++--++--+---++--++----++--+---++-++--+-----+-+---++-++++-+++++++---++-++--+-++++-+----++-+++-+++---+--+++-+--++-++--+++++++-+++--+---+---+-+---++-+-+--+-+++-++-----+++-++-+++-+-++--++++++-+-++-+++---++-+++-++----+--+++----++++...

output:

Yes
00101010110000011100101110100010100000011111001100101101100011001001001011001101110011001111001101110010011011111010111001000010000000111001001101000010111100100010001110110001011001001100000001000110111011101011100101011010001001111100010010001010011000000101001000111001000100111101100011110000...

result:

ok n=500

Test #9:

score: -100
Time Limit Exceeded

input:

4000
-++-+-+-+--+-++++---+-++------++---+-+++--+++--+++++++---+-++-+++++++----+---+++-++--++---+-++--+----+---+--++-+-+-+-----+-+---++-++--+---+++-++++-+-----++--++-++---++-+--+++-+--+--+-+-++-+++--++---+++-+-+---+++-++-+-++-+-+++---+++---+-+--++---+-+---+--+++--+----+-+--++---+-----+-+--+----+-+++-...

output:


result: