QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#770051#7857. (-1,1)-SumpleteTom22lWA 1ms7952kbC++233.4kb2024-11-21 20:25:222024-11-21 20:25:23

Judging History

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

  • [2024-11-21 20:25:23]
  • 评测
  • 测评结果:WA
  • 用时:1ms
  • 内存:7952kb
  • [2024-11-21 20:25:22]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;
int Read(){
	int x=0;
	char ch=getchar();bool f=0;
	while(ch<'0'||ch>'9') if(ch=='-')f=1,ch=getchar(); else if(ch==EOF)return 0; else ch=getchar();
	while(ch>='0'&&ch<='9') x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
	return f?-x:x;
}
bool f[4005][4005];
int c[4005][2];
int r[4005][2];
int dc[4005];
int dr[4005];
int cs[4005];
int rs[4005];
bool ans[4005][4005];
bool isans[4005][4005];
bool visc[4005];
bool visr[4005];
signed main(){
//	freopen("1.in","r",stdin);
//	freopen(".out","w",stdout);
	int n=Read();
	for(int i=1;i<=n;i++){
		for(int j=1;j<=n;j++){
			char ch=getchar();
			while(ch!='+'&&ch!='-') ch=getchar();
			if(ch=='+') f[i][j]=1,c[i][1]++,r[j][1]++;
			else c[i][0]++,r[j][0]++;
		}
	}
//	for(int i=1;i<=n;i++) cout<<r[i][0]<<' '<<r[i][1]<<endl;
	int suma=0;
	for(int i=1;i<=n;i++){
		cs[i]=Read();
		suma+=cs[i];
	}for(int i=1;i<=n;i++){
		rs[i]=Read();
		suma-=rs[i];
	}if(suma){
		printf("No\n");
		return 0;
	}
	int fin=0;
	while(fin<2*n){
		bool flag=0;
		int nfin=0,ltt=n+1;
		bool nc;
		for(int i=1;i<=n;i++){
			if(visc[i]) continue;
			if(dc[i]+c[i][1]<cs[i]){
				printf("No\n");
				return 0;
			}else if(dc[i]+c[i][1]==cs[i]){
				flag=1;
				fin++;visc[i]=1;
				for(int j=1;j<=n;j++){
					if(!isans[i][j]) isans[i][j]=1,ans[i][j]=f[i][j],r[j][f[i][j]]--,dr[j]+=f[i][j];
				}
			}else if(dc[i]-c[i][0]>cs[i]){
				printf("No\n");
				return 0;
			}else if(dc[i]-c[i][0]==cs[i]){
				flag=1;
				fin++;visc[i]=1;
				for(int j=1;j<=n;j++){
					if(!isans[i][j]) isans[i][j]=1,ans[i][j]=(!f[i][j]),r[j][f[i][j]]--,dr[j]-=(!f[i][j]);
				}
			}else{
				int ze=(cs[i]>dc[i]?min(c[i][1]-cs[i]+dc[i],c[i][0]):min(c[i][0]-dc[i]+cs[i],c[i][1]));
				if(ze<ltt){
					ltt=ze;
					nc=1;
					nfin=i;
				}
			}
		}for(int j=1;j<=n;j++){
			if(visr[j]) continue;
			if(dr[j]+r[j][1]<rs[j]){
				printf("No\n");
				return 0;
			}else if(dr[j]+r[j][1]==rs[j]){
				flag=1;
				fin++;visr[j]=1;
				for(int i=1;i<=n;i++){
					if(!isans[i][j]) isans[i][j]=1,ans[i][j]=f[i][j],c[i][f[i][j]]--,dc[i]+=f[i][j];
				}
			}else if(dr[j]-r[j][0]>rs[j]){
				printf("No\n");
				return 0;
			}else if(dr[j]-r[j][0]==rs[j]){
				flag=1;
				fin++;visr[j]=1;
				for(int i=1;i<=n;i++){
					if(!isans[i][j]) isans[i][j]=1,ans[i][j]=(!f[i][j]),c[i][f[i][j]]--,dc[i]-=(!f[i][j]);
				}
			}else{
				int ze=(dr[j]>dr[j]?min(r[j][1]-rs[j]+dr[j],r[j][0]):min(r[j][0]-dr[j]+rs[j],r[j][1]));
				if(ze<ltt){
					ltt=ze;
					nc=0;
					nfin=j;
				}
			}
		}if(!flag){
			if(nc=1){
			int i=nfin;
			visc[i]=1;fin++;
			for(int j=1;j<=n;j++){
				if(isans[i][j]) continue;
				if(cs[i]>dc[i]) isans[i][j]=1,ans[i][j]=f[i][j],r[j][f[i][j]]--,dr[j]+=f[i][j],dc[i]+=f[i][j];
				else if(cs[i]<dc[i]) isans[i][j]=1,ans[i][j]=(!f[i][j]),r[j][f[i][j]]--,dr[j]-=(!f[i][j]),dc[i]-=(!f[i][j]);
				else isans[i][j]=1,ans[i][j]=0,r[j][f[i][j]]--;
			}}else{
			int j=nfin;
			visr[j]=1;fin++;
			for(int i=1;i<=n;i++){
				if(isans[i][j]) continue;
				if(rs[j]>dr[j]) isans[i][j]=1,ans[i][j]=f[i][j],c[i][f[i][j]]--,dc[i]+=f[i][j],dr[j]+=f[i][j];
				else if(rs[j]<dr[j]) isans[i][j]=1,ans[i][j]=(!f[i][j]),c[i][f[i][j]]--,dr[j]-=(!f[i][j]),dc[i]-=(!f[i][j]);
				else isans[i][j]=1,ans[i][j]=0,c[i][f[i][j]]--;
			}}
		}
	}
	printf("Yes\n");
	for(int i=1;i<=n;i++){
		for(int j=1;j<=n;j++) printf("%d",ans[i][j]);
		printf("\n");
	}
	return 0;
}

详细

Test #1:

score: 100
Accepted
time: 0ms
memory: 7952kb

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

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

input:

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

output:

No

result:

ok n=3

Test #4:

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

input:

1
-
-1
1

output:

No

result:

ok n=1

Test #5:

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

input:

1
-
0
0

output:

Yes
0

result:

ok n=1

Test #6:

score: -100
Wrong Answer
time: 0ms
memory: 7868kb

input:

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

output:

Yes
00000000000000000000
00000000000000000000
00000000000000000000
00000000000000000000
00000000000000000000
00000000000000000000
00000000000000000000
00000000000000000000
00000000000000000000
00000000000000000000
00000000000000000000
01000000000000000000
00000000000000000000
00000000000000000000
00...

result:

wrong answer wrong sum at row 1