QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#288856 | #7857. (-1,1)-Sumplete | ucup-team896# | TL | 16ms | 29056kb | C++14 | 3.3kb | 2023-12-23 13:55:00 | 2023-12-23 13:55:01 |
Judging History
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 -++-+-+-+--+-++++---+-++------++---+-+++--+++--+++++++---+-++-+++++++----+---+++-++--++---+-++--+----+---+--++-+-+-+-----+-+---++-++--+---+++-++++-+-----++--++-++---++-+--+++-+--+--+-+-++-+++--++---+++-+-+---+++-++-+-++-+-+++---+++---+-+--++---+-+---+--+++--+----+-+--++---+-----+-+--+----+-+++-...