QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#770051 | #7857. (-1,1)-Sumplete | Tom22l | WA | 1ms | 7952kb | C++23 | 3.4kb | 2024-11-21 20:25:22 | 2024-11-21 20:25:23 |
Judging History
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;
}
Details
Tip: Click on the bar to expand more detailed information
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