QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#663353 | #7857. (-1,1)-Sumplete | qzez# | TL | 479ms | 83496kb | C++14 | 2.6kb | 2024-10-21 14:59:16 | 2024-10-21 14:59:23 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
const int N=4e3+10,V=N*2,E=N*N*2,INF=1e9;
int n,p[N],q[N],w[N][N];
char a[N][N];
struct edges{
int to,c,nex;
}edge[100001];
int kk=1,s,t,head[V],cur[V],d[V];
void add(int u,int v,int c){
// cerr<<u<<' '<<v<<' '<<c<<endl;
edge[++kk]={v,c,head[u]},head[u]=kk;
edge[++kk]={u,0,head[v]},head[v]=kk;
}
int pos[V];
bool bfs(){
queue<int>q;
copy(head+s,head+1+t,cur+s);
fill(d+s,d+1+t,-1);
d[s]=0,q.push(s);
for(int i=1;i<=n;i++)pos[i]=n+1,pos[i+n]=1;
for(int u;!q.empty();){
u=q.front(),q.pop();
for(int i=head[u];i;i=edge[i].nex){
int v=edge[i].to;
if(edge[i].c&&d[v]==-1)d[v]=d[u]+1,q.push(v);
}
if(u>=1&&u<=n){
for(int v=n+1;v<=n+n;v++)if(w[u][v-n]){
if(d[v]==-1)d[v]=d[u]+1,q.push(v);
}
}
if(u>n&&u<=n+n){
for(int v=1;v<=n;v++)if(!w[v][u-n]){
if(d[v]==-1)d[v]=d[u]+1,q.push(v);
}
}
}
return d[t]!=-1;
}
int dfs(int u,int lim=INF){
if(u==t)return lim;
int flow=0;
for(int i=cur[u];i&&flow<lim;i=edge[i].nex){
cur[u]=i;
int v=edge[i].to;
if(d[v]!=d[u]+1||!edge[i].c)continue;
int f=dfs(v,min(lim-flow,edge[i].c));
if(!f)d[v]=-1;
edge[i].c-=f,edge[i^1].c+=f,flow+=f;
}
if(u>=1&&u<=n){
for(int v=pos[u];v<=n+n&&flow<lim;v++){
pos[u]=v;
if(d[v]!=d[u]+1||!w[u][v-n])continue;
int f=dfs(v,1);
if(!f)d[v]=-1;
w[u][v-n]^=f,flow+=f;
}
}
if(u>n&&u<=n+n){
for(int v=pos[u];v<=n&&flow<lim;v++){
pos[u]=v;
if(d[v]!=d[u]+1||w[v][u-n])continue;
int f=dfs(v,1);
if(!f)d[v]=-1;
w[v][u-n]^=f,flow+=f;
}
}
return flow;
}
int dinic(){
int flow=0;
for(;bfs();)flow+=dfs(s);
return flow;
}
int main(){
scanf("%d",&n);
for(int i=1;i<=n;i++){
scanf("%s",a[i]+1);
}
s=0,t=n+n+1;
int sum=0;
for(int i=1;i<=n;i++){
scanf("%d",&p[i]);
if(p[i]>0){
sum+=p[i],add(s,i,p[i]);
}else{
add(i,t,-p[i]);
}
}
for(int i=1;i<=n;i++){
scanf("%d",&q[i]);
if(q[i]>0){
add(i+n,t,q[i]);
}else{
sum+=-q[i];
add(s,i+n,-q[i]);
}
}
if(accumulate(p+1,p+1+n,0)!=accumulate(q+1,q+1+n,0))puts("No"),exit(0);
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
if(a[i][j]=='+')w[i][j]=1;
else w[i][j]=0;
}
}
int res=dinic();
if(res!=sum)puts("No"),exit(0);
puts("Yes");
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
putchar("01"[w[i][j]!=(a[i][j]=='+')]);
}
puts("");
}
// for(int u=s;u<=t;u++){
// for(int i=head[u];i;i=edge[i].nex){
// if(i%2==0&&edge[i^1].c)fprintf(stderr,"%d %d %d\n",u,edge[i].to,edge[i^1].c);
// }
// }
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 1ms
memory: 7888kb
input:
3 +-+ -++ +-+ 1 1 1 1 -1 3
output:
Yes 001 001 111
result:
ok n=3
Test #2:
score: 0
Accepted
time: 0ms
memory: 7892kb
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: 7888kb
input:
3 +-+ -++ ++- 1 0 2 2 2 -1
output:
No
result:
ok n=3
Test #4:
score: 0
Accepted
time: 0ms
memory: 3688kb
input:
1 - -1 1
output:
No
result:
ok n=1
Test #5:
score: 0
Accepted
time: 0ms
memory: 7768kb
input:
1 - 0 0
output:
Yes 0
result:
ok n=1
Test #6:
score: 0
Accepted
time: 1ms
memory: 8116kb
input:
20 +-------+-----+++-++ -+-++++----++-++-++- -+++--+---+--+-++--- -+++-+--+----++---+- +++-+-++++++-+-+---+ -++-----+----++++++- +-++--+++++-++-+---- +-+----+---+-+++--+- +++++-+++++----+--+- ------++++---+--++-- ++++--------++++--+- -+-+-++++-+-++-++--+ ---+-++---+-++-++--- +-++++-++----+-+++-- +-+...
output:
Yes 01000001010100101110 00000000010010110010 00000001010001001101 10001001001101100111 11101000000001010000 10000000000001000001 00000000000000000101 01000000000000000110 00000000000000000000 10010100001100001000 00000011011100000100 10000000100000001000 10000000000011001000 00000000100001010000 00...
result:
ok n=20
Test #7:
score: 0
Accepted
time: 1ms
memory: 10140kb
input:
100 ++++-+-+--++++++-+--+--++-+-+--+++++-+++---+-+-+-++-+-+++-------+-++--+-++--+--+++++-++-+---+--+--++ -++--++-+-++++-+---++-+-+-+-+-+-+-+-+--+-+--+--+++---+--+-----+-----+-++-++-+-++++++--+-+++-+++-++++ --+---++-++--++-+++-------+--+-++------+-----+--+----++++++++-+--+++++--++--+-+-+++---+--+++-+...
output:
Yes 1111010100111111010010011000000000000000000000000000000000000000000000001100100111110110100010010011 0110011010111101000110101010100000000000000000000000000000000000000010000110100111110010111011101111 0010001101100110100000000000000000000000000000000000000000000010010010001100100011100010011101...
result:
ok n=100
Test #8:
score: 0
Accepted
time: 9ms
memory: 16524kb
input:
500 --+-+-+-++-----+++--+-+++-+---+-+-------+++--++++++-+--++--+-+-++++-++++--++--+---++--++----++--+---++-++--+-----+-+---++-++++-+++++++---++-++--+-++++-+----++-+++-+++---+--+++-+--++-++--+++++++-+++--+---+---+-+---++-+-+--+-+++-++-----+++-++-+++-+-++--++++++-+-++-+++---++-+++-++----+--+++----++++...
output:
Yes 11010101001111100011010001011101011111110001100000010110011010100001000011001101110011001111001101110010011011111010111001000010000000111001001101000010111100100010001110110001011011001100101110100001000100010100011010100100110110000011101101110101100111111010110000111111011011000010110001000001...
result:
ok n=500
Test #9:
score: 0
Accepted
time: 352ms
memory: 82392kb
input:
4000 -++-+-+-+--+-++++---+-++------++---+-+++--+++--+++++++---+-++-+++++++----+---+++-++--++---+-++--+----+---+--++-+-+-+-----+-+---++-++--+---+++-++++-+-----++--++-++---++-+--+++-+--+--+-+-++-+++--++---+++-+-+---+++-++-+-++-+-+++---+++---+-+--++---+-+---+--+++--+----+-+--++---+-----+-+--+----+-+++-...
output:
Yes 00000000000000000000000000000000000000000000000000000000000000000000000000000001010001000010100010000000000011000100000000010000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000...
result:
ok n=4000
Test #10:
score: 0
Accepted
time: 361ms
memory: 83020kb
input:
4000 +---+--++-+--++-+-++--+++--++--+++-+-+-+--++++++-++-+-+++-+---++++-+-+++----++-+---++--++--+++-----++---++-+--++++----++--++--+-+-++--+--+++++-+---+++-+++--++++-++-+++++++----+++-----+--++-+++-++-++-+++-+--++++++-+--++--+-+---++--------+-+--++----+-++-+-++---+--++--+-+--+-+++-+--+--++++-++----+...
output:
Yes 01110110010110010100110001100110001010101100000010010100010111000010100011110010111001100110001111100111001011000011110011001101010011011000001011100010001100001001000000011110001111101100100010010010001011000000101100110111110011111111010110011110100101001110110011110110100010110110000100111101...
result:
ok n=4000
Test #11:
score: 0
Accepted
time: 386ms
memory: 83496kb
input:
4000 -+--+------+--+++-++-----++--+-++-++-++-+-+-++++++--++--+-++-+-+++---++-+-+++++-++++++-+-++-++-++-+-++---+-+-------++-+++-++-+-++++-++-+-+-----+----+--+----++++-------++-+--+++----+++++++-+--+-+---+-+++++-+-----++-------++++--+-+-++---++++-++++-++-+++-+-++---+--+---+-++++++--++---+-++++++-+-+--...
output:
Yes 01001000000100111011000001100101101101101010111111001100101101011100011010111110111111010110110110101100010100000001101110110101111011010100000100001001000011110000000110100111000011111110100101000101111101000001100000001111001010110001111011110110111010110001001000101111110011000101111110101000...
result:
ok n=4000
Test #12:
score: 0
Accepted
time: 343ms
memory: 83224kb
input:
4000 +-+-----++++-----++++-+-++-+----+++---++--+---+++-+-++------+-+-++++----+-++++--+-++----+-+---+--+-----+-++--++-+++---+---+++---++-+++---++++---++----+++--+---+---+++-++-+-+-+--+++--++----++-+------+++-++-++--+--+++---+-------++++-+-++--++-+--+------+++++---+---++-++++-+++-++++-+---++-++++----+...
output:
Yes 01011111000011111000010100101111000111001101110001010011111101010000111101000011010011110101110110111110100110010001110111000111001000111000011100111100011011101110001001010101100011001111001011111100010010011011000111011111110000101001100101101111110000011101100010000100010000101110010000111100...
result:
ok n=4000
Test #13:
score: 0
Accepted
time: 391ms
memory: 82540kb
input:
4000 -+++---+-------+-++++-+++-++-+--++----++++++---+---++-++++-+++-++++-+---+--+++-----+-+--++-+--+-++++--+--++-+---+++++++++-+++++++-+++--+-+---++-+-++----+-++--++-++++++++++++++-+++-++-+++-++-++---+---+++-+-+++++++--+-+++-++-+-----+++-++--+++------+++--+++---+--+----++-+--+-+---+--+---+-+-+--++++...
output:
Yes 01110001000000010111101110110100110000111111000100011011110111011110100010011100000101001101001011110010011010001111111110111111101110010100011010110000101100110111111111111110111011011101101100010001110101111111001011101101000001110110011100000011100111000100100001101001010001001000101010011110...
result:
ok n=4000
Test #14:
score: 0
Accepted
time: 422ms
memory: 82412kb
input:
4000 +--+++++--++--+-+++-++-+-+-+-+--++------++++---+++-+-+--+------++-+--++-+-+++-----+-+++++-+------++++-++++-+--+------++--+++++-+-+--+-+++++++++++++++-+--+-+-+---+-+-+++++-++--+-+---++-++--+--+-+++-+-+++++-+--++-+----+++-++-++++-+---+--+-++-++-+-+-+---++-++-+-+----++-++++-----------+++--++++-++-...
output:
Yes 01100000110011010001001010101011001111110000111000101011011111100101100101000111110100000101111110000100001011011111100110000010101101000000000000000101101010111010100000100110101110010011011010001010000010110010111100010010000101110110100100101010111001001010111100100001111111111100011000010010...
result:
ok n=4000
Test #15:
score: 0
Accepted
time: 479ms
memory: 82416kb
input:
4000 ---++-++-+-+----++-++++-----------+++--++++-++-++--+-+--+--+-+-++++--++-++--+++++--++--+-+----+-+---++-+++-+--+-++++++++-++---++++-+--+-+++---+-+--+--+-+--+--++++++-+---++++++-++++----+-+-+-++--+---+--+-+++--++++++-+++-+---+--+-----------++-+++--+++++++--++-+++++--+++-+-+++++++++--+---+++--+-+-...
output:
Yes 00011011010100001101111000000000001110011110110110010100100101011110011011001111100110010100001010001101110100101111111101100011110100101110001010010010100100111111010001111110111100001010101100100010010111001111110111010001001000000000001101110011111110011011111001110101111111110010001110010100...
result:
ok n=4000
Test #16:
score: -100
Time Limit Exceeded
input:
4000 ++-+-------+--++-++-++--++-+++++-++++--+-----++-+--+---++++--+-----++++++---+--+---+------+++-+-----+-+++--+++-+-+-+++-----++---+-+---+-+++++-+--+-++--++-+-----++-+-+---+++-+----++++---++--+-+-++-++-+--++---+++------++-+-++++--+--++-++-+++-++-+--++----++---+-+++-+-+++-++-+--++-++++--++-+-+-+-+-...