QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#770070#7857. (-1,1)-SumpleteTom22lAC ✓1031ms50988kbC++233.5kb2024-11-21 20:30:342024-11-21 20:30:35

Judging History

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

  • [2024-11-21 20:30:35]
  • 评测
  • 测评结果:AC
  • 用时:1031ms
  • 内存:50988kb
  • [2024-11-21 20:30:34]
  • 提交

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=0;
		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;
}

这程序好像有点Bug,我给组数据试试?

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

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: 1ms
memory: 7736kb

input:

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

output:

No

result:

ok n=3

Test #4:

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

input:

1
-
-1
1

output:

No

result:

ok n=1

Test #5:

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

input:

1
-
0
0

output:

Yes
0

result:

ok n=1

Test #6:

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

input:

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

output:

Yes
01100000000000000000
01011000000000000000
00000001010101011101
10001001000001000101
11101011000000000000
11110111111101111011
01001000000000000000
10000000001001000101
10000000000000000100
11110000000000000000
00001111110000000000
10000000110111011100
00010100000000000000
10110000000000000000
01...

result:

ok n=20

Test #7:

score: 0
Accepted
time: 2ms
memory: 8260kb

input:

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

output:

Yes
1111010100111111000000000000000000000000000000000100001000000000100100001100100111110110100010010011
0110011010111101000110101010101010101001010010011100010010000010000010110110101000000000000000000000
0010001101100110000000000000000000000000000000000000000000001010010000001100101011100010011101...

result:

ok n=100

Test #8:

score: 0
Accepted
time: 16ms
memory: 13996kb

input:

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

output:

Yes
11010101001111100011010001011101011111110001100000010110011010100001000011001101110011001111001101110010011011111010111001000010000000111001001100000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000...

result:

ok n=500

Test #9:

score: 0
Accepted
time: 833ms
memory: 50960kb

input:

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

output:

Yes
01101010100101111000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000...

result:

ok n=4000

Test #10:

score: 0
Accepted
time: 915ms
memory: 50964kb

input:

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

output:

Yes
10001001101001101011001110011001110101010011111101101011101000111101011100001101000110011001110000011000110100111100001100110010101100100111110100011101110011110110111111100001110000010011011101101101110100111111010011001010001100000000101001100001011010110001001100101001011101001001111011000010...

result:

ok n=4000

Test #11:

score: 0
Accepted
time: 941ms
memory: 50896kb

input:

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

output:

Yes
01001000000100111011000001100101101101101010111111001100101101011100011010111110111111010110110110101100010100000001101110110101111011010100000100001001000011110000000110100111000011111110100101000101111101000001100000001111001010110001111011110110111010110001001000101111110011000101111110101000...

result:

ok n=4000

Test #12:

score: 0
Accepted
time: 880ms
memory: 50900kb

input:

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

output:

Yes
01011111000011111000010100101111000111001101110001010011111101010000111101000011010011110101110110111110100110010001110111000111001000111000011100111100011011101110001001010101100011001111001011111100010010011011000111011111110000101001100101101111110000011101110010000100010000101110010000111100...

result:

ok n=4000

Test #13:

score: 0
Accepted
time: 887ms
memory: 50948kb

input:

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

output:

Yes
01110001000000010111101110110100110000111111000100011011110111011110100010011100000101001101001011110010011010001111111110111111101110010100011010110000101100110111111111111110111011011101101100010001110101111111001011101101000001110110011100000011100111000100100001101001010001001000101010011110...

result:

ok n=4000

Test #14:

score: 0
Accepted
time: 925ms
memory: 50988kb

input:

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

output:

Yes
01100000110011010001001010101011001111110000111000101011011111100101100101000111110100000101111110000100001011011111100110000010101101000000000000000101101010111010100000100110101110010011011010001010000010110010111100010010000101110110100100101010111001001010111100100001111111111100011000010010...

result:

ok n=4000

Test #15:

score: 0
Accepted
time: 919ms
memory: 50868kb

input:

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

output:

Yes
00000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000...

result:

ok n=4000

Test #16:

score: 0
Accepted
time: 1014ms
memory: 50876kb

input:

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

output:

Yes
10011000000100110011110001111011011110010000011110010001111001000001111110000001000100000010101000001011100111010101110000011000101000101111101001011001101000001101010001110101001111001110010110101101001110011100000011011111100100110110111011010011000001000100110101110110100110110100110101010110...

result:

ok n=4000

Test #17:

score: 0
Accepted
time: 1031ms
memory: 50900kb

input:

3999
-+-+++---+-----++-++-+++--++-++-----+-++-+---+++-+++-+-+--+++++-++-+++-+---+-----+-++++-+--++-+++--+-++++--+-+-+-+-+----++----+--+---+--+--++-+++--++-+-++--++------+-+--++++--++-+--+----++---+-+---+++++--++-+-++-+++--++---++++-+-+--+-+++++-+-+--+---+---+-+--++++---+-++++-+--++------+++-+++-+-+-...

output:

Yes
10100010101111100110100011001001011101001011100010001011100000010010001011101111101000010110010001101000011010101010110100011101101110110110010101100101001100111111010110000110010110111100101010111000001100101001000110010100001010110100100101011011101110101100001110100001011001111110001000001010...

result:

ok n=3999

Test #18:

score: 0
Accepted
time: 1022ms
memory: 50936kb

input:

3998
--------+++--++-++++--+-+-++---+--++---++-+-++--+----++++---+-++-+-++++++++-+-+++---++++++-+--+-------+--+----++--+--+-+--+++---++-+++---+++-++-+++--++-+----+---+--+-++++--++++-++-+-+---+---+-++----+++++++++++--++--+++++-+++++++-+-+--+-+---+++-++-+++++-+-+-+-+++-+-++-+-+--+-+----+++-+-+--++-+--...

output:

Yes
11111110011000110001110000010110001000110100111101110110000111000100001000101000001010101100001111110001001001011100100000110010101001101011001101110110011110100001100110010111010010100001011111011000100010110001100000001110011001011010111001111011000000010110101001010001000110100000100110000010...

result:

ok n=3998

Test #19:

score: 0
Accepted
time: 118ms
memory: 50812kb

input:

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

output:

No

result:

ok n=4000

Test #20:

score: 0
Accepted
time: 126ms
memory: 50744kb

input:

3999
-+-+++---+-----++-++-+++--++-++-----+-++-+---+++-+++-+-+--+++++-++-+++-+---+-----+-++++-+--++-+++--+-++++--+-+-+-+-+----++----+--+---+--+--++-+++--++-+-++--++------+-+--++++--++-+--+----++---+-+---+++++--++-+-++-+++--++---++++-+-+--+-+++++-+-+--+---+---+-+--++++---+-++++-+--++------+++-+++-+-+-...

output:

No

result:

ok n=3999

Test #21:

score: 0
Accepted
time: 120ms
memory: 50744kb

input:

3998
--------+++--++-++++--+-+-++---+--++---++-+-++--+----++++---+-++-+-++++++++-+-+++---++++++-+--+-------+--+----++--+--+-+--+++---++-+++---+++-++-+++--++-+----+---+--+-++++--++++-++-+-+---+---+-++----+++++++++++--++--+++++-+++++++-+-+--+-+---+++-++-+++++-+-+-+-+++-+-++-+-+--+-+----+++-+-+--++-+--...

output:

No

result:

ok n=3998

Test #22:

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

input:

2
+-
--
0 -1
-1 2

output:

No

result:

ok n=2

Test #23:

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

input:

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

output:

No

result:

ok n=20

Test #24:

score: 0
Accepted
time: 115ms
memory: 21112kb

input:

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

output:

No

result:

ok n=4000

Test #25:

score: 0
Accepted
time: 872ms
memory: 50956kb

input:

3999
-++--+-+--+++-++--+---++--+---++--+++---++--++---++-+--++---+--++++---+++---++--++-+++++----++-+-+-----++--+++--++--++-+--+-++++-++++--++++-----------+++-+++++++-++--++--+-----++-+-----++++--+++++-+++-+-+--++++-++--++--+--+++-+-+-+-++-++----+---+++++--+++-+---++---+--+-++++-+-++-+-+-+---++-----...

output:

Yes
10011010110001001101110011011100110001110011001110010110011101100001110001110011001000001111001010111110011000110011001011010000100001100001111111111100010000000100110011011111001011111000011000001000101011000010011001101100010101010010011110111000001100010111001110110100001010010101011100111111...

result:

ok n=3999

Test #26:

score: 0
Accepted
time: 855ms
memory: 50944kb

input:

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

output:

Yes
00111000100010000001111001010111101011110101011101101011111010110000001001000010011110100111000000110000011000110000101000100001011000100010110101000101010100010100100100001001010011110000100000011010111001100010010101111000110101100111101000101111111000100110001011010011110111111110000110110100...

result:

ok n=4000

Test #27:

score: 0
Accepted
time: 847ms
memory: 50940kb

input:

3999
-++--+-+--+++-++--+---++--+---++--+++---++--++---++-+--++---+--++++---+++---++--++-+++++----++-+-+-----++--+++--++--++-+--+-++++-++++--++++-----------+++-+++++++-++--++--+-----++-+-----++++--+++++-+++-+-+--++++-++--++--+--+++-+-+-+-++-++----+---+++++--+++-+---++---+--+-++++-+-++-+-+-+---++-----...

output:

Yes
01100101001110110010001100100011001110001100110001101001100010011110001110001100110111110000110101000001100111001100110100101111011110011110000000000011101111111011001100100000110100000111100111110111010100111101100110010011101010101101100001000111110011101000110001001011110101101010100011000000...

result:

ok n=3999

Test #28:

score: 0
Accepted
time: 858ms
memory: 50864kb

input:

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

output:

Yes
11000111011101111110000110101000010100001010100010010100000101001111110110111101100001011000111111001111100111001111010111011110100111011101001010111010101011101011011011110110101100001111011111100101000110011101101010000111001010011000010111010000000111011001110100101100001000000001111001001011...

result:

ok n=4000

Extra Test:

score: 0
Extra Test Passed