QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#349027 | #7857. (-1,1)-Sumplete | chenxinyang2006# | TL | 433ms | 15108kb | C++14 | 5.0kb | 2024-03-09 23:07:28 | 2024-03-09 23:07:29 |
Judging History
answer
#include <bits/stdc++.h>
#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 uint unsigned int
#define ll long long
#define ull unsigned long long
#define db double
#define ldb long double
#define pii pair<int,int>
#define pll pair<ll,ll>
#define mkp make_pair
#define eb emplace_back
#define SZ(S) (int)S.size()
//#define mod 998244353
//#define mod 1000000007
#define inf 0x3f3f3f3f
#define linf 0x3f3f3f3f3f3f3f3f
using namespace std;
template <class T>
void chkmax(T &x,T y){
if(x < y) x = y;
}
template <class T>
void chkmin(T &x,T y){
if(x > y) x = y;
}
inline int popcnt(int x){
return __builtin_popcount(x);
}
inline int ctz(int x){
return __builtin_ctz(x);
}
/*ll power(ll p,int k = mod - 2){
ll ans = 1;
while(k){
if(k % 2 == 1) ans = ans * p % mod;
p = p * p % mod;
k /= 2;
}
return ans;
}*/
namespace io {
const int __SIZE = (1 << 22) + 1;
char ibuf[__SIZE], *iS, *iT, obuf[__SIZE], *oS = obuf, *oT = oS + __SIZE - 1, __c, qu[55]; int __f, qr, _eof;
#define Gc() (iS == iT ? (iT = (iS = ibuf) + fread (ibuf, 1, __SIZE, stdin), (iS == iT ? EOF : *iS ++)) : *iS ++)
inline void flush () { fwrite (obuf, 1, oS - obuf, stdout), oS = obuf; }
inline void gc (char &x) { x = Gc(); }
inline void pc (char x) { *oS ++ = x; if (oS == oT) flush (); }
inline void pstr (const char *s) { int __len = strlen(s); for (__f = 0; __f < __len; ++__f) pc (s[__f]); }
inline void gstr (char *s) { for(__c = Gc(); __c < 32 || __c > 126 || __c == ' ';) __c = Gc();
for(; __c > 31 && __c < 127 && __c != ' '; ++s, __c = Gc()) *s = __c; *s = 0; }
template <class I> inline bool read (I &x) { _eof = 0;
for (__f = 1, __c = Gc(); (__c < '0' || __c > '9') && !_eof; __c = Gc()) { if (__c == '-') __f = -1; _eof |= __c == EOF; }
for (x = 0; __c <= '9' && __c >= '0' && !_eof; __c = Gc()) x = x * 10 + (__c & 15), _eof |= __c == EOF; x *= __f; return !_eof; }
template <class I> inline void write (I x) { if (!x) pc ('0'); if (x < 0) pc ('-'), x = -x;
while (x) qu[++ qr] = x % 10 + '0', x /= 10; while (qr) pc (qu[qr --]); }
struct Flusher_ {~Flusher_(){flush();}}io_flusher_;
} using io::pc; using io::gc; using io::pstr; using io::gstr; using io::read; using io::write;
int n,s,t;
int G[8005][8005];
bitset <8005> GG[8005],temp,SS[8005],D[8005],curr;
char S[4005][4005];
int a[4005];
int dis[8005],cur[8005];
queue <int> Q;
int bfs(){
memset(dis,0x3f,sizeof(dis));
dis[s] = 0;
Q.push(s);
temp.set();
temp.reset(s);
while(!Q.empty()){
int u = Q.front();
Q.pop();
curr = GG[u] & temp;
while(curr.any()){
int v = curr._Find_first();
dis[v] = dis[u] + 1;
temp.reset(v);curr.reset(v);
Q.push(v);
}
}
rep(u,s,t) D[u].reset();
rep(u,s,t) if(dis[u] != inf) D[dis[u]].set(u);
return dis[t] != inf;
}
int dfs(int u,int flow){
if(u == t || !flow) return flow;
int sum = 0,tmp;
// printf("%d %d\n",u,flow);
while(cur[u] <= t){
int v = cur[u];
// printf("v=%d\n",v);
SS[u].reset(v);
cur[u] = SS[u]._Find_next(v);
tmp = dfs(v,min(flow,G[u][v]));
// printf("Return value u=%d tmp=%d\n",u,tmp);
G[u][v] -= tmp;
G[v][u] += tmp;
flow -= tmp;
sum += tmp;
if(!G[u][v]) GG[u].reset(v);
GG[v].set(u);
if(!flow || SS[u].none()) return sum;
}
return sum;
}
int token;
int dinic(){
/* rep(u,s,t){
rep(v,s,t) cerr << G[u][v] << " ";
cerr << endl;
}
cerr << endl;*/
int ans = 0;
while(bfs()){
// rep(v,s,t) cerr << dis[v] << " ";
// cerr << endl;
// return ans;
// cerr << "qwq\n";
rep(u,s,t){
if(dis[u] != inf) SS[u] = GG[u] & D[dis[u] + 1];
else SS[u].reset();
cur[u] = SS[u]._Find_first();
}
ans += dfs(s,inf);
/* rep(u,s,t){
rep(v,s,t) cerr << G[u][v] << " ";
cerr << endl;
}
cerr << endl;*/
// return 0;
token++;
// cerr <<"qwq\n";
}
cerr << token << endl;
return ans;
}
int main(){
// freopen("test.in","r",stdin);
// freopen("test.out","w",stdout);
read(n);
rep(i,1,n){
gstr(S[i] + 1);
rep(j,1,n){
if(S[i][j] == '+') G[i][j + n] = 1;
else G[j + n][i] = 1;
}
}
int sum1 = 0,sum2 = 0;
s = 0;t = 2 * n + 1;
rep(i,1,n){
read(a[i]);
if(a[i] > 0){
G[s][i] = a[i];
sum1 += a[i];
}else{
G[i][t] = -a[i];
sum2 -= a[i];
}
}
rep(i,1,n){
read(a[i]);
a[i] *= -1;
if(a[i] > 0){
G[s][i + n] = a[i];
sum1 += a[i];
}else{
G[i + n][t] = -a[i];
sum2 -= a[i];
}
}
rep(u,0,2 * n + 1){
rep(v,0,2 * n + 1) if(G[u][v]) GG[u].set(v);
}
if(sum1 != sum2){
pstr("No\n");
return 0;
}
int ret = dinic();
/* printf("Remaining:\n");
rep(u,0,2 * n + 1){
rep(v,0,2 * n + 1) if(G[u][v]) printf("%d->%d %d\n",u,v,G[u][v]);
}*/
if(ret != sum1){
pstr("No\n");
return 0;
}
pstr("Yes\n");
rep(u,1,n){
rep(v,n + 1,2 * n){
if(S[u][v - n] == '+') pc('0' + (G[u][v] ^ 1));
else pc('0' + (G[v][u] ^ 1));
}
pc('\n');
}
cerr << clock() << endl;
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 1ms
memory: 3740kb
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: 3752kb
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: 3936kb
input:
3 +-+ -++ ++- 1 0 2 2 2 -1
output:
No
result:
ok n=3
Test #4:
score: 0
Accepted
time: 1ms
memory: 3804kb
input:
1 - -1 1
output:
No
result:
ok n=1
Test #5:
score: 0
Accepted
time: 1ms
memory: 3728kb
input:
1 - 0 0
output:
Yes 0
result:
ok n=1
Test #6:
score: 0
Accepted
time: 1ms
memory: 4092kb
input:
20 +-------+-----+++-++ -+-++++----++-++-++- -+++--+---+--+-++--- -+++-+--+----++---+- +++-+-++++++-+-+---+ -++-----+----++++++- +-++--+++++-++-+---- +-+----+---+-+++--+- +++++-+++++----+--+- ------++++---+--++-- ++++--------++++--+- -+-+-++++-+-++-++--+ ---+-++---+-++-++--- +-++++-++----+-+++-- +-+...
output:
Yes 01000001010100111100 00000000010010110010 10000001010001001100 10000001011001000111 11100000100001010000 10000000000001000001 01000000000100000000 01010000000000100110 00000000000000000110 10000000001100000001 00000101010100000101 00000000000000001000 10000000000011001000 00000000100001001000 00...
result:
ok n=20
Test #7:
score: 0
Accepted
time: 7ms
memory: 5916kb
input:
100 ++++-+-+--++++++-+--+--++-+-+--+++++-+++---+-+-+-++-+-+++-------+-++--+-++--+--+++++-++-+---+--+--++ -++--++-+-++++-+---++-+-+-+-+-+-+-+-+--+-+--+--+++---+--+-----+-----+-++-++-+-++++++--+-+++-+++-++++ --+---++-++--++-+++-------+--+-++------+-----+--+----++++++++-+--+++++--++--+-+-+++---+--+++-+...
output:
Yes 0111010000100110000100011010100111110111000101010110000000000000000000001000100101000010100000010010 1110001110100000000101100100001011101000010010001100010010000010000010110110101111110010111011101111 0011001101111110011000001000010010001000000001000000001101111000011101001000100001000010010100...
result:
ok n=100
Test #8:
score: 0
Accepted
time: 433ms
memory: 15108kb
input:
500 --+-+-+-++-----+++--+-+++-+---+-+-------+++--++++++-+--++--+-+-++++-++++--++--+---++--++----++--+---++-++--+-----+-+---++-++++-+++++++---++-++--+-++++-+----++-+++-+++---+--+++-+--++-++--+++++++-+++--+---+---+-+---++-+-+--+-+++-++-----+++-++-+++-+-++--++++++-+-++-+++---++-+++-++----+--+++----++++...
output:
Yes 00101010001000100010010110001000010100100001000000010110011000100001000011001001010010001001000100100010010010010010001001000010000000111001001001000010100100000010001110000001011000001100000001000110101001001000100100010010001001010000010010001010010000000101001000111000000100110100000011010000...
result:
ok n=500
Test #9:
score: -100
Time Limit Exceeded
input:
4000 -++-+-+-+--+-++++---+-++------++---+-+++--+++--+++++++---+-++-+++++++----+---+++-++--++---+-++--+----+---+--++-+-+-+-----+-+---++-++--+---+++-++++-+-----++--++-++---++-+--+++-+--+--+-+-++-+++--++---+++-+-+---+++-++-+-++-+-+++---+++---+-+--++---+-+---+--+++--+----+-+--++---+-----+-+--+----+-+++-...