QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#405524 | #7857. (-1,1)-Sumplete | dnialh# | AC ✓ | 1518ms | 83716kb | C++23 | 3.9kb | 2024-05-06 03:55:07 | 2024-05-06 03:55:11 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
#define f first
#define s second
#define pb push_back
#define eb emplace_back
#define mp make_pair
#define all(v) v.begin(), v.end()
#define sz(v) (int)v.size()
#define sq(a) ((a)*(a))
#define per(i,a,b) for (int i = (b)-1; i >= a; i--)
#define rep(i,a,b) for (int i=a; i<b; i++)
#define FOR(i,a,b) for (int i=a; i<b; i++)
#define F0R(i,a) for (int i=0; i<a; i++)
#define ROF(i,a,b) for (int i = (b)-1; i >= a; i--)
#define R0F(i,a) for (int i = (a)-1; i >= 0; i--)
#define FAST ios::sync_with_stdio(0); cin.tie(0);
#define finish(x) return cout << x << endl, 0;
#define dbg(x) cerr << ">>> " << #x << " = " << x << endl;
#define _ << " _ " <<
#define ll int
using vi = vector<int>;
using vvi = vector<vi>;
struct Dinic {
struct Edge {
int to, rev;
ll c, oc;
ll flow() { return max(oc - c, 0); } // if you need flows
};
vi lvl, ptr, q;
vector<vector<Edge>> adj;
Dinic(int n) : lvl(n), ptr(n), q(n), adj(n) {}
void addEdge(int a, int b, ll c, ll rcap = 0) {
adj[a].push_back({b, sz(adj[b]), c, c});
adj[b].push_back({a, sz(adj[a]) - 1, rcap, rcap});
}
ll dfs(int v, int t, ll f) {
if (v == t || !f) return f;
for (int& i = ptr[v]; i < sz(adj[v]); i++) {
Edge& e = adj[v][i];
if (lvl[e.to] == lvl[v] + 1)
if (ll p = dfs(e.to, t, min(f, e.c))) {
e.c -= p, adj[e.to][e.rev].c += p;
return p;
}
}
return 0;
}
ll calc(int s, int t) {
ll flow = 0; q[0] = s;
rep(L,30,31) do { // 'int L=30' maybe faster for random data
lvl = ptr = vi(sz(q));
int qi = 0, qe = lvl[s] = 1;
while (qi < qe && !lvl[t]) {
int v = q[qi++];
for (Edge e : adj[v])
if (!lvl[e.to] && e.c >> (30 - L))
q[qe++] = e.to, lvl[e.to] = lvl[v] + 1;
}
while (ll p = dfs(s, t, INT_MAX)) flow += p;
} while (lvl[t]);
return flow;
}
bool leftOfMinCut(int a) { return lvl[a] != 0; }
};
template<class T> bool ckmin(T&a, T&b) { bool B = a > b; a = min(a,b); return B; }
template<class T> bool ckmax(T&a, T&b) { bool B = a < b; a = max(a,b); return B; }
typedef long double ld;
typedef pair<int,int> pi;
typedef pair<ld,ld> pld;
typedef complex<ld> cd;
typedef vector<int> vi;
typedef vector<ld> vld;
typedef vector<vector<int>> vvi;
const ld PI = acos(-1.0);
const ld EPS = 1e-7;
const int MOD = 998244353;
int32_t main() { FAST
int n;
cin >> n;
vector<string> board(n);
F0R(i, n){
cin >> board[i];
}
vector<int> r(n), c(n);
F0R(i, n){
cin >> r[i];
}
F0R(i, n){
cin >> c[i];
}
F0R(i, n){
F0R(j, n){
if (board[i][j] == '-'){
r[i]++;
c[j]++;
}
}
}
int totr = 0;
int totc = 0;
F0R(i, n){
totr += r[i];
totc += c[i];
if (r[i] < 0 || c[i] < 0){
cout << "No\n";
return 0;
}
}
if (totr != totc){
cout << "No\n";
return 0;
}
/*
int so = n + n;
int si = n + n + 1;
Dinic MF(n + n + 2);
F0R(i, n){
MF.addEdge(so, i, r[i]);
MF.addEdge(i + n, si, c[i]);
}
F0R(i, n){
F0R(j, n){
MF.addEdge(i, j + n, 1);
}
}
auto res = MF.calc(so, si);
if (res != totc){
cout << "No\n";
return 0;
}
cout << "Yes\n";
vvi out(n, vi(n));
F0R(i, n){
for(auto e : MF.adj[i]){
if (e.to < so && e.flow()){
out[i][e.to - n] = 1;
}
}
}*/
vvi out(n, vi(n));
F0R(i, n){
vector<pi> rr;
F0R(j, n){
rr.emplace_back(-r[j], j);
}
sort(all(rr));
for (auto [v, j] : rr){
if (c[i] == 0) break;
c[i]--;
if (r[j] == 0) {
cout << "No\n";
return 0;
}
r[j]--;
out[j][i] ++;
}
}
cout << "Yes\n";
F0R(i, n){
F0R(j, n){
if (board[i][j] == '-'){
out[i][j] ^= 1;
}
cout << out[i][j];
}
cout << '\n';
}
return 0;
}
这程序好像有点Bug,我给组数据试试?
詳細信息
Test #1:
score: 100
Accepted
time: 0ms
memory: 3520kb
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: 3644kb
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: 3496kb
input:
3 +-+ -++ ++- 1 0 2 2 2 -1
output:
No
result:
ok n=3
Test #4:
score: 0
Accepted
time: 0ms
memory: 3540kb
input:
1 - -1 1
output:
No
result:
ok n=1
Test #5:
score: 0
Accepted
time: 1ms
memory: 3748kb
input:
1 - 0 0
output:
Yes 0
result:
ok n=1
Test #6:
score: 0
Accepted
time: 1ms
memory: 3560kb
input:
20 +-------+-----+++-++ -+-++++----++-++-++- -+++--+---+--+-++--- -+++-+--+----++---+- +++-+-++++++-+-+---+ -++-----+----++++++- +-++--+++++-++-+---- +-+----+---+-+++--+- +++++-+++++----+--+- ------++++---+--++-- ++++--------++++--+- -+-+-++++-+-++-++--+ ---+-++---+-++-++--- +-++++-++----+-+++-- +-+...
output:
Yes 10100101111001101110 01011011101111100011 11010111100011001101 10001101001011110111 11101001010111000100 11001010001011101011 01001101010001000101 11101011101111100111 00000001001100110111 11110000100101101001 00001111111111010111 10100100111111111100 00010111011111110010 10101110110101110110 01...
result:
ok n=20
Test #7:
score: 0
Accepted
time: 1ms
memory: 3632kb
input:
100 ++++-+-+--++++++-+--+--++-+-+--+++++-+++---+-+-+-++-+-+++-------+-++--+-++--+--+++++-++-+---+--+--++ -++--++-+-++++-+---++-+-+-+-+-+-+-+-+--+-+--+--+++---+--+-----+-----+-++-++-+-++++++--+-+++-+++-++++ --+---++-++--++-+++-------+--+-++------+-----+--+----++++++++-+--+++++--++--+-+-+++---+--+++-+...
output:
Yes 1110000000101101011010111110110111010110000001010010100110100000001101101110100011111110110010110010 0110011010111101000110101110111010001000010110011000011010100010100011110100101011111010101011001110 0010001001110100110001000110000110100000000101001100010111011010111110001110101111101010001101...
result:
ok n=100
Test #8:
score: 0
Accepted
time: 11ms
memory: 5064kb
input:
500 --+-+-+-++-----+++--+-+++-+---+-+-------+++--++++++-+--++--+-+-++++-++++--++--+---++--++----++--+---++-++--+-----+-+---++-++++-+++++++---++-++--+-++++-+----++-+++-+++---+--+++-+--++-++--+++++++-+++--+---+---+-+---++-+-+--+-+++-++-----+++-++-+++-+-++--++++++-+-++-+++---++-+++-++----+--+++----++++...
output:
Yes 11010101001111100011110101111001111101111001000010011110001011100101001011011101010010001101001001111010001011011011111011000110001000101001101100000000110100101010011110010000011011000100001001100111111001101001100001010010011001011101010000001110010000010100001001111011000000101101110011010001...
result:
ok n=500
Test #9:
score: 0
Accepted
time: 1060ms
memory: 83596kb
input:
4000 -++-+-+-+--+-++++---+-++------++---+-+++--+++--+++++++---+-++-+++++++----+---+++-++--++---+-++--+----+---+--++-+-+-+-----+-+---++-++--+---+++-++++-+-----++--++-++---++-+--+++-+--+--+-+-++-+++--++---+++-+-+---+++-++-+-++-+-+++---+++---+-+--++---+-+---+--+++--+----+-+--++---+-----+-+--+----+-+++-...
output:
Yes 10010101011010000111010011111100111010001100011000000011101011101010110100010010001100110111100111010001000110000000010100000100111001110110111010000101001100111001001111001000011100000011101100110110111111011011100000111110110110110111110011011111011100100111010000011001000101000001110100001000...
result:
ok n=4000
Test #10:
score: 0
Accepted
time: 957ms
memory: 83504kb
input:
4000 +---+--++-+--++-+-++--+++--++--+++-+-+-+--++++++-++-+-+++-+---++++-+-+++----++-+---++--++--+++-----++---++-+--++++----++--++--+-+-++--+--+++++-+---+++-+++--++++-++-+++++++----+++-----+--++-+++-++-++-+++-+--++++++-+--++--+-+---++--------+-+--++----+-++-+-++---+--++--+-+--+-+++-+--+--++++-++----+...
output:
Yes 10001001101001101001111011001100101111111001001000110001000101101011110001010111101011000011000110110101101111101010111010011111000001111100101111001011000101000000001001010100011101111110110000000000011001010010111110100111100001101101000100001100110111011100100001000100110000100100010110101111...
result:
ok n=4000
Test #11:
score: 0
Accepted
time: 1007ms
memory: 83648kb
input:
4000 -+--+------+--+++-++-----++--+-++-++-++-+-+-++++++--++--+-++-+-+++---++-+-+++++-++++++-+-++-++-++-+-++---+-+-------++-+++-++-+-++++-++-+-+-----+----+--+----++++-------++-+--+++----+++++++-+--+-+---+-+++++-+-----++-------++++--+-+-++---++++-++++-++-+++-+-++---+--+---+-++++++--++---+-++++++-+-+--...
output:
Yes 01001000000100111011000001110000100111000000011010011000000111001000110000101010010110000100010010000101000110010101001010011100110010000110010110011011010001010100100010000011100111011010000001100000110100001000101001000110000011111000110010111111110011111000000001100110111010001100110111100001...
result:
ok n=4000
Test #12:
score: 0
Accepted
time: 945ms
memory: 83716kb
input:
4000 +-+-----++++-----++++-+-++-+----+++---++--+---+++-+-++------+-+-++++----+-++++--+-++----+-+---+--+-----+-++--++-+++---+---+++---++-+++---++++---++----+++--+---+---+++-++-+-+-+--+++--++----++-+------+++-++-++--+--+++---+-------++++-+-++--++-+--+------+++++---+---++-++++-+++-++++-+---++-++++----+...
output:
Yes 01011111000111010010111110001010010010011000100100011001010111110101101000010001111001100000100100010111110010111011100010001101011101110010001001110110001111000100011101111100110001101010000001101000111011001001100010010101100100000000110001000110100010111000111000010000111001111100110101110110...
result:
ok n=4000
Test #13:
score: 0
Accepted
time: 965ms
memory: 83604kb
input:
4000 -+++---+-------+-++++-+++-++-+--++----++++++---+---++-++++-+++-++++-+---+--+++-----+-+--++-+--+-++++--+--++-+---+++++++++-+++++++-+++--+-+---++-+-++----+-++--++-++++++++++++++-+++-++-+++-++-++---+---+++-+-+++++++--+-+++-++-+-----+++-++--+++------+++--+++---+--+----++-+--+-+---+--+---+-+-+--++++...
output:
Yes 01110001000000010111101110110100110000111111000100011011110111011110001000111001010001100111101110100000110011011101010111101011000111000000110011100100000101100101011010110100011110010111111000111000100111011010000001111001101000100100111001001001110011101101110011001100011011011100000011001100...
result:
ok n=4000
Test #14:
score: 0
Accepted
time: 953ms
memory: 83504kb
input:
4000 +--+++++--++--+-+++-++-+-+-+-+--++------++++---+++-+-+--+------++-+--++-+-+++-----+-+++++-+------++++-++++-+--+------++--+++++-+-+--+-+++++++++++++++-+--+-+-+---+-+-+++++-++--+-+---++-++--+--+-+++-+-+++++-+--++-+----+++-++-++++-+---+--+-++-++-+-+-+---++-++-+-+----++-++++-----------+++--++++-++-...
output:
Yes 01100000110011010001001010101011001111110000111000101011011111100101100101000111110100000101111110000100001011011111100110000010101101000000000000000101101010111010100000100110101110010011011010001010000010110010111100010010000101110110100100101010111001001010111100100001111111111100011000010010...
result:
ok n=4000
Test #15:
score: 0
Accepted
time: 1039ms
memory: 83556kb
input:
4000 ---++-++-+-+----++-++++-----------+++--++++-++-++--+-+--+--+-+-++++--++-++--+++++--++--+-+----+-+---++-+++-+--+-++++++++-++---++++-+--+-+++---+-+--+--+-+--+--++++++-+---++++++-++++----+-+-+-++--+---+--+-+++--++++++-+++-+---+--+-----------++-+++--+++++++--++-+++++--+++-+-+++++++++--+---+++--+-+-...
output:
Yes 11100100101011110010000101001010011111010111110010000110100001001111011001001011101110011100011010011101100100111111110101100111110000101100001011010010110100110111010011111110011100000010101110100010110111000111110110010001000000000010001101100011111100011011101001110111111111111010001111010100...
result:
ok n=4000
Test #16:
score: 0
Accepted
time: 1518ms
memory: 83556kb
input:
4000 ++-+-------+--++-++-++--++-+++++-++++--+-----++-+--+---++++--+-----++++++---+--+---+------+++-+-----+-+++--+++-+-+-+++-----++---+-+---+-+++++-+--+-++--++-+-----++-+-+---+++-+----++++---++--+-+-++-++-+--++---+++------++-+-++++--+--++-++-+++-++-+--++----++---+-+++-+-+++-++-+--++-++++--++-+-+-+-+-...
output:
Yes 10011000000100110011110001111011011110010000011110010001111001000001111110000001000100000010101000001011100111010101110000011000101000101111101001011001101000001101010001110101001111001110010110101101001110011100000011011111100100110110111011010011000001000100110101110110100110110100110101010110...
result:
ok n=4000
Test #17:
score: 0
Accepted
time: 1518ms
memory: 83612kb
input:
3999 -+-+++---+-----++-++-+++--++-++-----+-++-+---+++-+++-+-+--+++++-++-+++-+---+-----+-++++-+--++-+++--+-++++--+-+-+-+-+----++----+--+---+--+--++-+++--++-+-++--++------+-+--++++--++-+--+----++---+-+---+++++--++-+-++-+++--++---++++-+-+--+-+++++-+-+--+---+---+-+--++++---+-++++-+--++------+++-+++-+-+-...
output:
Yes 10100010101111100110100011001001011101001011100010001011100000010010001011101111101000010110010001101000011010101010110100011101101110110110010101100101001100111111010110000110010110111100101010111000001100101001000110010100001010110100100101011011101110101100001110100001011001111110001000001010...
result:
ok n=3999
Test #18:
score: 0
Accepted
time: 1483ms
memory: 83608kb
input:
3998 --------+++--++-++++--+-+-++---+--++---++-+-++--+----++++---+-++-+-++++++++-+-+++---++++++-+--+-------+--+----++--+--+-+--+++---++-+++---+++-++-+++--++-+----+---+--+-++++--++++-++-+-+---+---+-++----+++++++++++--++--+++++-+++++++-+-+--+-+---+++-++-+++++-+-+-+-+++-+-++-+-+--+-+----+++-+-+--++-+--...
output:
Yes 11111110011000110001110000010110001000110100111101110110000111000100001000101000001010101100001111110001001001011100100000110010101001101011001101110110011110100001100110010111010010100001011111011000100010110001100000001110011001011010111001111011000000010110101001010001000110100000100110000010...
result:
ok n=3998
Test #19:
score: 0
Accepted
time: 670ms
memory: 83648kb
input:
4000 ++-+-------+--++-++-++--++-+++++-++++--+-----++-+--+---++++--+-----++++++---+--+---+------+++-+-----+-+++--+++-+-+-+++-----++---+-+---+-+++++-+--+-++--++-+-----++-+-+---+++-+----++++---++--+-+-++-++-+--++---+++------++-+-++++--+--++-++-+++-++-+--++----++---+-+++-+-+++-++-+--++-++++--++-+-+-+-+-...
output:
No
result:
ok n=4000
Test #20:
score: 0
Accepted
time: 792ms
memory: 83692kb
input:
3999 -+-+++---+-----++-++-+++--++-++-----+-++-+---+++-+++-+-+--+++++-++-+++-+---+-----+-++++-+--++-+++--+-++++--+-+-+-+-+----++----+--+---+--+--++-+++--++-+-++--++------+-+--++++--++-+--+----++---+-+---+++++--++-+-++-+++--++---++++-+-+--+-+++++-+-+--+---+---+-+--++++---+-++++-+--++------+++-+++-+-+-...
output:
No
result:
ok n=3999
Test #21:
score: 0
Accepted
time: 331ms
memory: 83644kb
input:
3998 --------+++--++-++++--+-+-++---+--++---++-+-++--+----++++---+-++-+-++++++++-+-+++---++++++-+--+-------+--+----++--+--+-+--+++---++-+++---+++-++-+++--++-+----+---+--+-++++--++++-++-+-+---+---+-++----+++++++++++--++--+++++-+++++++-+-+--+-+---+++-++-+++++-+-+-+-+++-+-++-+-+--+-+----+++-+-+--++-+--...
output:
No
result:
ok n=3998
Test #22:
score: 0
Accepted
time: 1ms
memory: 3456kb
input:
2 +- -- 0 -1 -1 2
output:
No
result:
ok n=2
Test #23:
score: 0
Accepted
time: 1ms
memory: 3752kb
input:
20 --+--------+---++-++ --+++-+----+--++-+++ -+-+-++++---+-+---++ +++-++--++-++-++--++ +---+----+-+++-++++- ----+++++--++----+-+ +-++++----++--++---- ++++++-+-+-++-++--+- -+--+-++++-+-+-+-+-+ --++-+-+--++-++--++- +---+++-+++-+-+-++-+ +++-+--+++-++-+++-+- --++--+-++-+--+-+-++ ----++-+--+-+-++++-+ --+...
output:
No
result:
ok n=20
Test #24:
score: 0
Accepted
time: 78ms
memory: 20988kb
input:
4000 ++---+++-+++-++++++----++-+-+----+-+----+-+-+---+--+-+-----+-+--++++++-++-++++-++----+-++---++++++--+++++--+++--++++-+-+++-++++-+--+++-+++-+--+-+-+++-+-+-+-+++-+-++-++-++++-++-+-++----++++-++++++--+-+---++--+++-++-+-+----+++--+-+--++----+-+++-+-------+++-++--+++-+--+-++----+--------++++--+--+-+...
output:
No
result:
ok n=4000
Test #25:
score: 0
Accepted
time: 725ms
memory: 83692kb
input:
3999 -++--+-+--+++-++--+---++--+---++--+++---++--++---++-+--++---+--++++---+++---++--++-+++++----++-+-+-----++--+++--++--++-+--+-++++-++++--++++-----------+++-+++++++-++--++--+-----++-+-----++++--+++++-+++-+-+--++++-++--++--+--+++-+-+-+-++-++----+---+++++--+++-+---++---+--+-++++-+-++-+-+-+---++-----...
output:
Yes 10011010110001001101110011011100110001110011001110010110011101100001110001110011001000001111001010111110011000110011001011010000100001100001111111111100010000000100110011011111001011111000011000001000101011000010011001101100010101010010011110111000001100010111001110110100001010010101011100111111...
result:
ok n=3999
Test #26:
score: 0
Accepted
time: 715ms
memory: 83536kb
input:
4000 ++---+++-+++-++++++----++-+-+----+-+----+-+-+---+--+-+-----+-+--++++++-++-++++-++----+-++---++++++--+++++--+++--++++-+-+++-++++-+--+++-+++-+--+-+-+++-+-+-+-+++-+-++-++-++++-++-+-++----++++-++++++--+-+---++--+++-++-+-+----+++--+-+--++----+-+++-+-------+++-++--+++-+--+-++----+--------++++--+--+-+...
output:
Yes 00111000100010000001111001010111101011110101011101101011111010110000001001000010011110100111000000110000011000110000101000100001011000100010110101000101010100010100100100001001010011110000100000011010111001100010010101111000110101100111101000101111111000100110001011010011110111111110000110110100...
result:
ok n=4000
Test #27:
score: 0
Accepted
time: 871ms
memory: 83492kb
input:
3999 -++--+-+--+++-++--+---++--+---++--+++---++--++---++-+--++---+--++++---+++---++--++-+++++----++-+-+-----++--+++--++--++-+--+-++++-++++--++++-----------+++-+++++++-++--++--+-----++-+-----++++--+++++-+++-+-+--++++-++--++--+--+++-+-+-+-++-++----+---+++++--+++-+---++---+--+-++++-+-++-+-+-+---++-----...
output:
Yes 01100101001110110010001100100011001110001100110001101001100010011110001110001100110111110000110101000001100111001100110100101111011110011110000000000011101111111011001100100000110100000111100111110111010100111101100110010011101010101101100001000111110011101000110001001011110101101010100011000000...
result:
ok n=3999
Test #28:
score: 0
Accepted
time: 848ms
memory: 83568kb
input:
4000 ++---+++-+++-++++++----++-+-+----+-+----+-+-+---+--+-+-----+-+--++++++-++-++++-++----+-++---++++++--+++++--+++--++++-+-+++-++++-+--+++-+++-+--+-+-+++-+-+-+-+++-+-++-++-++++-++-+-++----++++-++++++--+-+---++--+++-++-+-+----+++--+-+--++----+-+++-+-------+++-++--+++-+--+-++----+--------++++--+--+-+...
output:
Yes 11000111011101111110000110101000010100001010100010010100000101001111110110111101100001011000111111001111100111001111010111011110100111011101001010111010101011101011011011110110101100001111011111100101000110011101101010000111001010011000010111010000000111011001110100101100001000000001111001001011...
result:
ok n=4000
Extra Test:
score: 0
Extra Test Passed