QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#597779#7857. (-1,1)-SumpleteDelovTL 2866ms443348kbC++142.7kb2024-09-28 18:46:482024-09-28 18:46:48

Judging History

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

  • [2024-09-28 18:46:48]
  • 评测
  • 测评结果:TL
  • 用时:2866ms
  • 内存:443348kb
  • [2024-09-28 18:46:48]
  • 提交

answer


#include <bits/stdc++.h>
typedef long long ll;typedef unsigned long long ull; typedef double db;typedef long double ldb;
#define fre(x) freopen(#x ".in","r",stdin),freopen(#x ".out","w",stdout)
#define Rep(i,a,b) for(int i=a;i<=b;++i) 
#define Dwn(i,a,b) for(int i=a;i>=b;--i)
#define pii pair<int,int>
#define mair make_pair
#define fir first
#define sec second
using namespace std;

const int maxn=4e3+10,INF=INT_MAX>>1;

int n;
char s[maxn];
int R[maxn],C[maxn],sR[maxn],sC[maxn];
int S,T;
int a[maxn][maxn];

struct Graph_Net{
	struct eg{ int to,next;int cap; }e[maxn*maxn*2+maxn*4];
	int len,head[maxn*2];
	Graph_Net(){ len=1; }
	void lqx(int from,int to,int cap)
	{ e[++len].to=to;e[len].next=head[from];e[len].cap=cap;head[from]=len; }
	void Set_c(int u,int v,int w){ lqx(u,v,w),lqx(v,u,0); }
	int dep[maxn*2],cur[maxn*2];
	int q[maxn*2],l,r;
	bool bfs(int s,int t){
		memset(dep,0,sizeof(dep)); dep[s]=1;
		l=1,r=1;q[1]=s; cur[s]=head[s];
		while(l<=r){
			s=q[l];++l;
			for(int i=head[s];i;i=e[i].next){
				int v=e[i].to;
				if(dep[v] || !e[i].cap)continue;
				dep[v]=dep[s]+1;
				cur[v]=head[v];
				if(v==t)return true;
				q[++r]=v;
			}
		}
		return false;
	}
	int dfs(int u,int flow){
		if(u==T || !flow)return flow;
		int rest=flow,res;
		for(int &i=cur[u],v;i;i=e[i].next){
			v=e[i].to;
			if(!e[i].cap || dep[v]!=dep[u]+1)continue;
			res=dfs(v,min(rest,e[i].cap));
			if(res==0)dep[v]=0;
			rest-=res; e[i].cap-=res,e[i^1].cap+=res;
			if(rest<=0)break;
		}
		return flow-rest;
	}
	int Dinic(int s,int t){ int res=0;while(bfs(s,t))res+=dfs(s,INF); return res; }
	void Build(){
		Rep(u,1,n){
			for(int i=head[u];i;i=e[i].next)if(e[i].to!=S){
				int v=e[i].to-n;
				if(e[i].cap==0)a[u][v]^=1;
			}
		}
	}
}G;

void solve(){
	cin>>n;
	Rep(i,1,n){
		cin>>s;
		for(int j=0;j<n;++j)a[i][j+1]=(s[j]=='+'),sR[i]+=a[i][j+1],sC[j+1]+=a[i][j+1];
	}
	Rep(i,1,n)cin>>R[i];
	Rep(i,1,n)cin>>C[i];
	Rep(i,1,n)if(sR[i]<R[i] || sC[i]<C[i])return cout<<"No\n",void();
	S=n+n+1,T=n+n+2;
	int sum=0,sam=0,cc=0;
	Rep(i,1,n){
		//G.Set_c(S,i,sR[i]-R[i]);
		//G.Set_c(i+n,T,sC[i]-C[i]);
		sum+=sR[i]-R[i];
		sam+=sC[i]-C[i];
		cc+=R[i]-(sR[i]-n);
	}
	if(sum!=sam)return cout<<"No\n",void();
	if(cc<sum){
		Rep(i,1,n)Rep(j,1,n)a[i][j]^=1;
		Rep(i,1,n)G.Set_c(S,i,R[i]-(sR[i]-n)),G.Set_c(i+n,T,C[i]-(sC[i]-n));
		sum=cc;
	}else{
		Rep(i,1,n)G.Set_c(S,i,sR[i]-R[i]),G.Set_c(i+n,T,sC[i]-C[i]);
	}
	Rep(i,1,n)Rep(j,1,n)G.Set_c(i,j+n,1);
	int res=G.Dinic(S,T);
	if(res!=sum)return cout<<"No\n",void();
	G.Build();
	cout<<"Yes\n";
	Rep(i,1,n){
		Rep(j,1,n)cout<<a[i][j];
		cout<<"\n";
	}
}

int main (){ ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);return solve(),0; }

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 1ms
memory: 5744kb

input:

3
+-+
-++
+-+
1 1 1
1 -1 3

output:

Yes
001
001
111

result:

ok n=3

Test #2:

score: 0
Accepted
time: 1ms
memory: 5800kb

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: 5728kb

input:

3
+-+
-++
++-
1 0 2
2 2 -1

output:

No

result:

ok n=3

Test #4:

score: 0
Accepted
time: 1ms
memory: 5668kb

input:

1
-
-1
1

output:

No

result:

ok n=1

Test #5:

score: 0
Accepted
time: 0ms
memory: 5668kb

input:

1
-
0
0

output:

Yes
0

result:

ok n=1

Test #6:

score: 0
Accepted
time: 1ms
memory: 5740kb

input:

20
+-------+-----+++-++
-+-++++----++-++-++-
-+++--+---+--+-++---
-+++-+--+----++---+-
+++-+-++++++-+-+---+
-++-----+----++++++-
+-++--+++++-++-+----
+-+----+---+-+++--+-
+++++-+++++----+--+-
------++++---+--++--
++++--------++++--+-
-+-+-++++-+-++-++--+
---+-++---+-++-++---
+-++++-++----+-+++--
+-+...

output:

Yes
10000011011111011011
01011111111001010110
01110011110110100000
01110101111110011101
11101010100010110001
10100000111101001001
01001011100111100111
01010001001101000111
00000100110000000111
11111100110001011001
00001111111111100111
10101000001011011100
11101110001011011100
01000010100001011100
01...

result:

ok n=20

Test #7:

score: 0
Accepted
time: 1ms
memory: 8044kb

input:

100
++++-+-+--++++++-+--+--++-+-+--+++++-+++---+-+-+-++-+-+++-------+-++--+-++--+--+++++-++-+---+--+--++
-++--++-+-++++-+---++-+-+-+-+-+-+-+-+--+-+--+--+++---+--+-----+-----+-++-++-+-++++++--+-+++-+++-++++
--+---++-++--++-+++-------+--+-++------+-----+--+----++++++++-+--+++++--++--+-+-+++---+--+++-+...

output:

Yes
0000101011100011010010011010100111110111000101010110101110000000101100101100100111110110101101101100
1001100101100001000110101010101010101001010010011100010010000010000010110110101111110010111011101000
1101110010111010111000000010010110000001000001001000011111111010011111001100101011100010011110...

result:

ok n=100

Test #8:

score: 0
Accepted
time: 14ms
memory: 20520kb

input:

500
--+-+-+-++-----+++--+-+++-+---+-+-------+++--++++++-+--++--+-+-++++-++++--++--+---++--++----++--+---++-++--+-----+-+---++-++++-+++++++---++-++--+-++++-+----++-+++-+++---+--+++-+--++-++--+++++++-+++--+---+---+-+---++-+-+--+-+++-++-----+++-++-+++-+-++--++++++-+-++-+++---++-+++-++----+--+++----++++...

output:

Yes
00101010110000011100101110100010100000011111001100101101100011001001001011001101110011001111001101110010011011111010111001000010000000111001001101000010111100100010001110110001011001001100000001000110111011101011100101011010001001111100010010001010011000000101001000111001000100111101100011110000...

result:

ok n=500

Test #9:

score: 0
Accepted
time: 2866ms
memory: 441716kb

input:

4000
-++-+-+-+--+-++++---+-++------++---+-+++--+++--+++++++---+-++-+++++++----+---+++-++--++---+-++--+----+---+--++-+-+-+-----+-+---++-++--+---+++-++++-+-----++--++-++---++-+--+++-+--+--+-+-++-+++--++---+++-+-+---+++-++-+-++-+-+++---+++---+-+--++---+-+---+--+++--+----+-+--++---+-----+-+--+----+-+++-...

output:

Yes
10010101011010000111010011111100111010001100011000000011101001000000011110111000100110011101001101111011101100101010111110101110010011011100010000101111100110011011100101100010110110101001010110011100010101110001001010100100110100011101011001110101110110001101011010110011101111101011011100101011...

result:

ok n=4000

Test #10:

score: 0
Accepted
time: 2633ms
memory: 443348kb

input:

4000
+---+--++-+--++-+-++--+++--++--+++-+-+-+--++++++-++-+-+++-+---++++-+-+++----++-+---++--++--+++-----++---++-+--++++----++--++--+-+-++--+--+++++-+---+++-+++--++++-++-+++++++----+++-----+--++-+++-++-++-+++-+--++++++-+--++--+-+---++--------+-+--++----+-++-+-++---+--++--+-+--+-+++-+--+--++++-++----+...

output:

Yes
10001001101001101011001110011001110101010011111101101011101000111101011100001101000110011001110000011000110100111100001100110010101100100111110100011101110011110111111110100001010100010011011101101101110100011111110011001010001100000000101001100001011010110001001100100001011101001101111011000011...

result:

ok n=4000

Test #11:

score: 0
Accepted
time: 2278ms
memory: 441688kb

input:

4000
-+--+------+--+++-++-----++--+-++-++-++-+-+-++++++--++--+-++-+-+++---++-+-+++++-++++++-+-++-++-++-+-++---+-+-------++-+++-++-+-++++-++-+-+-----+----+--+----++++-------++-+--+++----+++++++-+--+-+---+-+++++-+-----++-------++++--+-+-++---++++-++++-++-+++-+-++---+--+---+-++++++--++---+-++++++-+-+--...

output:

Yes
10110111111011000100111110011010010010010101000000110011010010100011100101000001000000101001001001010011101011111110010001001010000100101011111011110110111100001111111001011000111100000001011010111010000010111110011111110000110101101010000100001001000101001110110111011000001100011110000001000101...

result:

ok n=4000

Test #12:

score: 0
Accepted
time: 2173ms
memory: 442932kb

input:

4000
+-+-----++++-----++++-+-++-+----+++---++--+---+++-+-++------+-+-++++----+-++++--+-++----+-+---+--+-----+-++--++-+++---+---+++---++-+++---++++---++----+++--+---+---+++-++-+-+-+--+++--++----++-+------+++-++-++--+--+++---+-------++++-+-++--++-+--+------+++++---+---++-++++-+++-++++-+---++-++++----+...

output:

Yes
10100000111100000111101011010000111000110010001110101100000010101111000010111100101100001010001001000001011001101110001000111000110111000111100011000011100100010001110110101010011100110000110100000011101101100100111000100000001111010110011010010000001111100010001101111011101111010001101111000011...

result:

ok n=4000

Test #13:

score: 0
Accepted
time: 2148ms
memory: 442120kb

input:

4000
-+++---+-------+-++++-+++-++-+--++----++++++---+---++-++++-+++-++++-+---+--+++-----+-+--++-+--+-++++--+--++-+---+++++++++-+++++++-+++--+-+---++-+-++----+-++--++-++++++++++++++-+++-++-+++-++-++---+---+++-+-+++++++--+-+++-++-+-----+++-++--+++------+++--+++---+--+----++-+--+-+---+--+---+-+-+--++++...

output:

Yes
10001110111111101000010001001011001111000000111011100100001000100001011101100011111010110010110100001101100101110000000001000000010001101011100101001111010011001000000000000001000100100010010011101110001010000000110100010010111110001001100011111100011000111011011110010110101110110111010101100001...

result:

ok n=4000

Test #14:

score: 0
Accepted
time: 1984ms
memory: 442624kb

input:

4000
+--+++++--++--+-+++-++-+-+-+-+--++------++++---+++-+-+--+------++-+--++-+-+++-----+-+++++-+------++++-++++-+--+------++--+++++-+-+--+-+++++++++++++++-+--+-+-+---+-+-+++++-++--+-+---++-++--+--+-+++-+-+++++-+--++-+----+++-++-++++-+---+--+-++-++-+-+-+---++-++-+-+----++-++++-----------+++--++++-++-...

output:

Yes
10011111001100101110110101010100110000001111000111010100100000011010011010111000001011111010000001111011110101100000011001111101010010111111111111111011010101000100011111011001000011100101110101110100110001011110101011011011011100100110101100111111110011111110101100100001111111111100011000010010...

result:

ok n=4000

Test #15:

score: 0
Accepted
time: 2052ms
memory: 442592kb

input:

4000
---++-++-+-+----++-++++-----------+++--++++-++-++--+-+--+--+-+-++++--++-++--+++++--++--+-+----+-+---++-+++-+--+-++++++++-++---++++-+--+-+++---+-+--+--+-+--+--++++++-+---++++++-++++----+-+-+-++--+---+--+-+++--++++++-+++-+---+--+-----------++-+++--+++++++--++-+++++--+++-+-+++++++++--+---+++--+-+-...

output:

Yes
11100100101011110010000111111111110001100001001001101011011010100001100100110000011001101011110101110010001011010000000010011100001011010001110101101101011011000000101111001111000001101101100011001101010001001000110011011101001100000000001001101101111110011011111001110101111111110010001110010110...

result:

ok n=4000

Test #16:

score: -100
Time Limit Exceeded

input:

4000
++-+-------+--++-++-++--++-+++++-++++--+-----++-+--+---++++--+-----++++++---+--+---+------+++-+-----+-+++--+++-+-+-+++-----++---+-+---+-+++++-+--+-++--++-+-----++-+-+---+++-+----++++---++--+-+-++-++-+--++---+++------++-+-++++--+--++-++-+++-++-+--++----++---+-+++-+-+++-++-+--++-++++--++-+-+-+-+-...

output:


result: