QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#353261 | #7857. (-1,1)-Sumplete | ucup-team3215 | TL | 1025ms | 809376kb | C++20 | 3.0kb | 2024-03-13 23:54:09 | 2024-03-13 23:54:09 |
Judging History
answer
#include <algorithm>
#include <array>
#include <iostream>
#include <limits>
#include <vector>
using namespace std;
constexpr int N = 4e3;
template<typename T = int>
struct /*Maksim1744*/ Dinic {
struct Edge {
int v, u;
T f, c;
};
vector<Edge> ed;
vector<array<int, 2 * N>> e;
vector<int> se;
int n, st, fin;
T flow;
vector<int> ptr, ds, que;
Dinic(int n_, int st_, int fin_) : n(n_), st(st_), fin(fin_), flow(0) {
e.resize(n);
fill(&e[0][0], &e[n][0], -1);
se.resize(n);
ptr.resize(n);
ds.resize(n);
que.resize(n);
}
void ae(int v, int u, T c, T bc = 0, T f = 0) {
int w = int(ed.size());
ed.push_back({v, u, f, c});
ed.push_back({u, v, -f, bc});
e[v][se[v]++] = w;
e[u][se[u]++] = w + 1;
}
bool bfs(T scale) {
fill(ds.begin(), ds.end(), -1);
ds[st] = 0;
int sz = 1;
que[0] = st;
for (int it = 0; it < sz; it++) {
int v = que[it];
for (int i : e[v]) if (~i)
if (ed[i].f + scale <= ed[i].c && ds[ed[i].u] == -1) {
ds[ed[i].u] = ds[v] + 1;
if (ed[i].u == fin)
return 1;
que[sz++] = ed[i].u;
}
}
return 0;
}
T dfs(int v, T w, T cs) {
if (v == fin)
return w;
int &i = ptr[v];
while (i >= 0) {
auto &t = ed[e[v][i]];
if (ds[t.u] == ds[v] + 1 && t.f + cs <= t.c) {
T o = dfs(t.u, min(w, t.c - t.f), cs);
if (o) {
t.f += o;
ed[e[v][i] ^ 1].f -= o;
return o;
}
}
i--;
}
return 0;
}
T get(int scale = 30) {
for (T i = ((T(1)) << scale); i > 0; i >>= 1)
while (bfs(i)) {
for (int j = 0; j < n; j++)
ptr[j] = int(e[j].size()) - 1;
while (T w = dfs(st, numeric_limits<T>::max(), i))
flow += w;
}
return flow;
}
};
bool a[N][N];
int rt[N], ct[N];
int main() {
cin.tie(0)->sync_with_stdio(0);
int n; cin >> n;
Dinic<> mf(2 * n + 2, 2 * n, 2 * n + 1);
for (int i = 0; i < n; ++i) if (string s; cin >> s)
for (int j = 0; j < n; ++j) a[i][j] = s[j] == '+';
for (int i = 0; i < n; ++i) cin >> rt[i];
for (int i = 0; i < n; ++i) cin >> ct[i];
vector<string> ans(n, string(n, '0'));
for (int i = 0; i < n; ++i)
for (int j = 0; j < n; ++j) {
if (rt[i] > 0 && ct[j] > 0 && a[i][j]) --rt[i], --ct[j], ans[i][j] = '1';
else if (rt[i] < 0 && ct[j] < 0 && !a[i][j]) ++rt[i], ++ct[j], ans[i][j] = '1';
else if (a[i][j]) mf.ae(i, n + j, 1);
else mf.ae(n + j, i, 1);
}
int s[2]{};
for (int i = 0; i < n; ++i) if (rt[i] > 0) mf.ae(2 * n, i, rt[i]), s[0] += rt[i]; else mf.ae(i, 2 * n + 1, -rt[i]), s[1] -= rt[i];
for (int i = 0; i < n; ++i) if (ct[i] < 0) mf.ae(2 * n, n + i, -ct[i]), s[0] -= ct[i]; else mf.ae(n + i, 2 * n + 1, ct[i]), s[1] += ct[i];
if (s[0] != s[1] || s[0] != mf.get(1)) return cout << "NO\n", 0;
cout << "Yes\n";
for (int i = 0; i < mf.ed.size(); i += 2) if (auto& e = mf.ed[i]; max(e.u, e.v) < 2 * n && e.f) {
ans[min(e.u, e.v) % n][max(e.u, e.v) % n] = '1';
}
for (auto& s: ans) cout << s << '\n';
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 1ms
memory: 3584kb
input:
3 +-+ -++ +-+ 1 1 1 1 -1 3
output:
Yes 111 001 001
result:
ok n=3
Test #2:
score: 0
Accepted
time: 1ms
memory: 3524kb
input:
3 --- -++ +++ -2 -1 0 -2 -1 0
output:
Yes 110 100 000
result:
ok n=3
Test #3:
score: 0
Accepted
time: 1ms
memory: 3640kb
input:
3 +-+ -++ ++- 1 0 2 2 2 -1
output:
NO
result:
ok n=3
Test #4:
score: 0
Accepted
time: 0ms
memory: 3740kb
input:
1 - -1 1
output:
NO
result:
ok n=1
Test #5:
score: 0
Accepted
time: 0ms
memory: 3692kb
input:
1 - 0 0
output:
Yes 0
result:
ok n=1
Test #6:
score: 0
Accepted
time: 0ms
memory: 4784kb
input:
20 +-------+-----+++-++ -+-++++----++-++-++- -+++--+---+--+-++--- -+++-+--+----++---+- +++-+-++++++-+-+---+ -++-----+----++++++- +-++--+++++-++-+---- +-+----+---+-+++--+- +++++-+++++----+--+- ------++++---+--++-- ++++--------++++--+- -+-+-++++-+-++-++--+ ---+-++---+-++-++--- +-++++-++----+-+++-- +-+...
output:
Yes 01010000000000000000 00000000000010110000 10000100000000000000 10000011010000000000 00100000100101010001 10000000000000000000 01000000000100000000 00000010010001100001 00000000000000000110 10000000001100000001 00000001011100000101 00000000110001001100 00000000000011001001 00000000000001011000 00...
result:
ok n=20
Test #7:
score: 0
Accepted
time: 3ms
memory: 10200kb
input:
100 ++++-+-+--++++++-+--+--++-+-+--+++++-+++---+-+-+-++-+-+++-------+-++--+-++--+--+++++-++-+---+--+--++ -++--++-+-++++-+---++-+-+-+-+-+-+-+-+--+-+--+--+++---+--+-----+-----+-++-++-+-++++++--+-+++-+++-++++ --+---++-++--++-+++-------+--+-++------+-----+--+----++++++++-+--+++++--++--+-+-+++---+--+++-+...
output:
Yes 1111010100111111010010011010100111110111000101010110000000000000000000000000000000000000000000000000 0110011010111101000110101010101010101001010010011100010010000010000010110110101000000000000000000000 0010001101100110111000000010010110000001000001001000011111110000000000000000000000000000000000...
result:
ok n=100
Test #8:
score: 0
Accepted
time: 25ms
memory: 45264kb
input:
500 --+-+-+-++-----+++--+-+++-+---+-+-------+++--++++++-+--++--+-+-++++-++++--++--+---++--++----++--+---++-++--+-----+-+---++-++++-+++++++---++-++--+-++++-+----++-+++-+++---+--+++-+--++-++--+++++++-+++--+---+---+-+---++-+-+--+-+++-++-----+++-++-+++-+-++--++++++-+-++-+++---++-+++-++----+--+++----++++...
output:
Yes 11010101001111100011010001011101011111110001100000010110011010100001000011001101110011001111001101110010011011111010111001000010000000111001001101000010111100100010001110110001011001001100000001000110111011101011100101011010001001111100010010001010011000000101001000111001000100111101100010000000...
result:
ok n=500
Test #9:
score: 0
Accepted
time: 785ms
memory: 809300kb
input:
4000 -++-+-+-+--+-++++---+-++------++---+-+++--+++--+++++++---+-++-+++++++----+---+++-++--++---+-++--+----+---+--++-+-+-+-----+-+---++-++--+---+++-++++-+-----++--++-++---++-+--+++-+--+--+-+-++-+++--++---+++-+-+---+++-++-+-++-+-+++---+++---+-+--++---+-+---+--+++--+----+-+--++---+-----+-+--+----+-+++-...
output:
Yes 00000000100001000000100000000010000001010010000100001000010000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000...
result:
ok n=4000
Test #10:
score: 0
Accepted
time: 747ms
memory: 809376kb
input:
4000 +---+--++-+--++-+-++--+++--++--+++-+-+-+--++++++-++-+-+++-+---++++-+-+++----++-+---++--++--+++-----++---++-+--++++----++--++--+-+-++--+--+++++-+---+++-+++--++++-++-+++++++----+++-----+--++-+++-++-++-+++-+--++++++-+--++--+-+---++--------+-+--++----+-++-+-++---+--++--+-+--+-+++-+--+--++++-++----+...
output:
Yes 01110110010110010100110001100110001010101100000010010100010111000010100011110010111001100110001111100111001011000011110011001101010011011000001011100010001100001001000000011110001111101100100010010010001011000000101100110101110011111111010110011110100101001110110011010110100010110110000100111101...
result:
ok n=4000
Test #11:
score: 0
Accepted
time: 631ms
memory: 809288kb
input:
4000 -+--+------+--+++-++-----++--+-++-++-++-+-+-++++++--++--+-++-+-+++---++-+-+++++-++++++-+-++-++-++-+-++---+-+-------++-+++-++-+-++++-++-+-+-----+----+--+----++++-------++-+--+++----+++++++-+--+-+---+-+++++-+-----++-------++++--+-+-++---++++-++++-++-+++-+-++---+--+---+-++++++--++---+-++++++-+-+--...
output:
Yes 01001000000100111011000001100101101101101010111111001100101101011100011010111110111111010110110110101100010100000001101110110101111011010100000100001001000011110000000110100111000011111110100101000101111101000001100000001111001010110001111011110110111010110001001000101111110011000101111110101000...
result:
ok n=4000
Test #12:
score: 0
Accepted
time: 677ms
memory: 809372kb
input:
4000 +-+-----++++-----++++-+-++-+----+++---++--+---+++-+-++------+-+-++++----+-++++--+-++----+-+---+--+-----+-++--++-+++---+---+++---++-+++---++++---++----+++--+---+---+++-++-+-+-+--+++--++----++-+------+++-++-++--+--+++---+-------++++-+-++--++-+--+------+++++---+---++-++++-+++-++++-+---++-++++----+...
output:
Yes 01011111000011111000010100101111000111001101110001010011111101010000111101000011010011110101110110111110100110010001110111000111001000111000011100111100011011101110001001010101100011001111001011111100010010011011000111011111110000101001100101101111110000011101110010000100010000101110010000111100...
result:
ok n=4000
Test #13:
score: 0
Accepted
time: 701ms
memory: 809292kb
input:
4000 -+++---+-------+-++++-+++-++-+--++----++++++---+---++-++++-+++-++++-+---+--+++-----+-+--++-+--+-++++--+--++-+---+++++++++-+++++++-+++--+-+---++-+-++----+-++--++-++++++++++++++-+++-++-+++-++-++---+---+++-+-+++++++--+-+++-++-+-----+++-++--+++------+++--+++---+--+----++-+--+-+---+--+---+-+-+--++++...
output:
Yes 01110001000000010111101110110100110000111111000100011011110111011110100010011100000101001101001011110010011010001111111110111111101110010100011010110000101100110111111111111110111011011101101100010001110101111111001011101101000001110110011100000011100111000100100001101001010001001000101010011110...
result:
ok n=4000
Test #14:
score: 0
Accepted
time: 1025ms
memory: 809232kb
input:
4000 +--+++++--++--+-+++-++-+-+-+-+--++------++++---+++-+-+--+------++-+--++-+-+++-----+-+++++-+------++++-++++-+--+------++--+++++-+-+--+-+++++++++++++++-+--+-+-+---+-+-+++++-++--+-+---++-++--+--+-+++-+-+++++-+--++-+----+++-++-++++-+---+--+-++-++-+-+-+---++-++-+-+----++-++++-----------+++--++++-++-...
output:
Yes 01100000110011010001001010101011001111110000111000101011011111100101100101000111110100000101111110000100001011011111100110000010101101000000000000000101101010111010100000100110101110010011011010001010000010110010111100010010000101110110100100101010111001001010111100100001111111111100011000010010...
result:
ok n=4000
Test #15:
score: 0
Accepted
time: 866ms
memory: 809280kb
input:
4000 ---++-++-+-+----++-++++-----------+++--++++-++-++--+-+--+--+-+-++++--++-++--+++++--++--+-+----+-+---++-+++-+--+-++++++++-++---++++-+--+-+++---+-+--+--+-+--+--++++++-+---++++++-++++----+-+-+-++--+---+--+-+++--++++++-+++-+---+--+-----------++-+++--+++++++--++-+++++--+++-+-+++++++++--+---+++--+-+-...
output:
Yes 00011011010100001101111000000000001110011110110110010100100101011110011011001111100110010100001010001101110100101111111101100011110100101110001010010010100100111111010001111110111100001010101100100010010111001111110111010001001000000000001101110011111110011011111001110101111111110010001110010100...
result:
ok n=4000
Test #16:
score: -100
Time Limit Exceeded
input:
4000 ++-+-------+--++-++-++--++-+++++-++++--+-----++-+--+---++++--+-----++++++---+--+---+------+++-+-----+-+++--+++-+-+-+++-----++---+-+---+-+++++-+--+-++--++-+-----++-+-+---+++-+----++++---++--+-+-++-++-+--++---+++------++-+-++++--+--++-++-+++-++-+--++----++---+-+++-+-+++-++-+--++-++++--++-+-+-+-+-...