QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#663353#7857. (-1,1)-Sumpleteqzez#TL 479ms83496kbC++142.6kb2024-10-21 14:59:162024-10-21 14:59:23

Judging History

你现在查看的是最新测评结果

  • [2024-10-21 14:59:23]
  • 评测
  • 测评结果:TL
  • 用时:479ms
  • 内存:83496kb
  • [2024-10-21 14:59:16]
  • 提交

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
++-+-------+--++-++-++--++-+++++-++++--+-----++-+--+---++++--+-----++++++---+--+---+------+++-+-----+-+++--+++-+-+-+++-----++---+-+---+-+++++-+--+-++--++-+-----++-+-+---+++-+----++++---++--+-+-++-++-+--++---+++------++-+-++++--+--++-++-+++-++-+--++----++---+-+++-+-+++-++-+--++-++++--++-+-+-+-+-...

output:


result: