QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#596054 | #7857. (-1,1)-Sumplete | Delov | TL | 3000ms | 443612kb | C++14 | 2.6kb | 2024-09-28 15:02:36 | 2024-09-28 15:02:42 |
Judging History
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;
int a[maxn][maxn];
char s[maxn];
int R[maxn],C[maxn],sR[maxn],sC[maxn];
int S,T;
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 init(){ len=1;memset(head,0,sizeof(head));memset(e,0,sizeof(e)); }
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;
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;
int 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;
Rep(i,1,n){
G.Set_c(S,i,sR[i]-R[i]);
sum+=sR[i]-R[i];
}
Rep(i,1,n)Rep(j,1,n)G.Set_c(i,j+n,1);
Rep(i,1,n){
G.Set_c(i+n,T,sC[i]-C[i]);
sam+=sC[i]-C[i];
}
if(sum!=sam)return cout<<"No\n",void();
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: 5728kb
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: 5636kb
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: 5712kb
input:
3 +-+ -++ ++- 1 0 2 2 2 -1
output:
No
result:
ok n=3
Test #4:
score: 0
Accepted
time: 0ms
memory: 5652kb
input:
1 - -1 1
output:
No
result:
ok n=1
Test #5:
score: 0
Accepted
time: 0ms
memory: 5708kb
input:
1 - 0 0
output:
Yes 0
result:
ok n=1
Test #6:
score: 0
Accepted
time: 1ms
memory: 5640kb
input:
20 +-------+-----+++-++ -+-++++----++-++-++- -+++--+---+--+-++--- -+++-+--+----++---+- +++-+-++++++-+-+---+ -++-----+----++++++- +-++--+++++-++-+---- +-+----+---+-+++--+- +++++-+++++----+--+- ------++++---+--++-- ++++--------++++--+- -+-+-++++-+-++-++--+ ---+-++---+-++-++--- +-++++-++----+-+++-- +-+...
output:
Yes 01110001100000110100 10101101010110110111 10000001011001011111 10000111010001101101 11011100001101010001 10011111010001111110 01001100001011010111 10111110111101110110 10000100000000010111 00011100001001011001 00001111111111100111 01011000010111001100 00010110000111101101 10111101101111101011 00...
result:
ok n=20
Test #7:
score: 0
Accepted
time: 2ms
memory: 8076kb
input:
100 ++++-+-+--++++++-+--+--++-+-+--+++++-+++---+-+-+-++-+-+++-------+-++--+-++--+--+++++-++-+---+--+--++ -++--++-+-++++-+---++-+-+-+-+-+-+-+-+--+-+--+--+++---+--+-----+-----+-++-++-+-++++++--+-+++-+++-++++ --+---++-++--++-+++-------+--+-++------+-----+--+----++++++++-+--+++++--++--+-+-+++---+--+++-+...
output:
Yes 0000101011100011010010011010100111110111000101010110101110000000101100101100100111110110101101101100 1001100101100001000110101010101010101001010010011100010010000010000010110110101111110010111011101000 1101110010111010111000000010010110000001000001001000011111111010011111001100101011100010011110...
result:
ok n=100
Test #8:
score: 0
Accepted
time: 21ms
memory: 20832kb
input:
500 --+-+-+-++-----+++--+-+++-+---+-+-------+++--++++++-+--++--+-+-++++-++++--++--+---++--++----++--+---++-++--+-----+-+---++-++++-+++++++---++-++--+-++++-+----++-+++-+++---+--+++-+--++-++--+++++++-+++--+---+---+-+---++-+-+--+-+++-++-----+++-++-+++-+-++--++++++-+-++-+++---++-+++-++----+--+++----++++...
output:
Yes 11010101001111100011010001011101011111110001100000010110011010100001000011001101110011001111001101110010010100000101000110111101111111000110110010111101000011011101110001001110100110110011111110111001000101101011100101011010001001111100010010001010011000000101001000111001000100111101100011110000...
result:
ok n=500
Test #9:
score: 0
Accepted
time: 2461ms
memory: 443588kb
input:
4000 -++-+-+-+--+-++++---+-++------++---+-+++--+++--+++++++---+-++-+++++++----+---+++-++--++---+-++--+----+---+--++-+-+-+-----+-+---++-++--+---+++-++++-+-----++--++-++---++-+--+++-+--+--+-+-++-+++--++---+++-+-+---+++-++-+-++-+-+++---+++---+-+--++---+-+---+--+++--+----+-+--++---+-----+-+--+----+-+++-...
output:
Yes 10010101011010000111010011111100111010001100011000000011101001000000011110111000100110011101001101111011101100101010111110101110010011011100010000101111100110011011100101100010110110101001010110011100010101110001001010100100110100011101011001110101110110001101011010110011101111101011011100101011...
result:
ok n=4000
Test #10:
score: 0
Accepted
time: 3000ms
memory: 443548kb
input:
4000 +---+--++-+--++-+-++--+++--++--+++-+-+-+--++++++-++-+-+++-+---++++-+-+++----++-+---++--++--+++-----++---++-+--++++----++--++--+-+-++--+--+++++-+---+++-+++--++++-++-+++++++----+++-----+--++-+++-++-++-+++-+--++++++-+--++--+-+---++--------+-+--++----+-++-+-++---+--++--+-+--+-+++-+--+--++++-++----+...
output:
Yes 01110110010110010100110001100110001010101100000010010100010111000010100011110010111001100110001111100111001011000011110011001101010011011000001011100010001100001001000000011110001111101100100010010010001011000000101100110101110011111111010110011110100101001110110011010110100010110110000100111101...
result:
ok n=4000
Test #11:
score: 0
Accepted
time: 2641ms
memory: 443612kb
input:
4000 -+--+------+--+++-++-----++--+-++-++-++-+-+-++++++--++--+-++-+-+++---++-+-+++++-++++++-+-++-++-++-+-++---+-+-------++-+++-++-+-++++-++-+-+-----+----+--+----++++-------++-+--+++----+++++++-+--+-+---+-+++++-+-----++-------++++--+-+-++---++++-++++-++-+++-+-++---+--+---+-++++++--++---+-++++++-+-+--...
output:
Yes 10110111111011000100111110011010010010010101000000110011010010100011100101000001000000101001001001010011101011111110010001001010000100101011111011110110111100001111111001011000111100000001011010111010000010111110011111110000110101101010000100001001000101001110110111011000001100011110000001000101...
result:
ok n=4000
Test #12:
score: 0
Accepted
time: 2752ms
memory: 443604kb
input:
4000 +-+-----++++-----++++-+-++-+----+++---++--+---+++-+-++------+-+-++++----+-++++--+-++----+-+---+--+-----+-++--++-+++---+---+++---++-+++---++++---++----+++--+---+---+++-++-+-+-+--+++--++----++-+------+++-++-++--+--+++---+-------++++-+-++--++-+--+------+++++---+---++-++++-+++-++++-+---++-++++----+...
output:
Yes 01011111000011111000010100101111000111001101110001010011111101010000111101000011010011110101110110111110100110010001110111000111001000111000011100111100011011101110001001010101100011001111001011111100010010011011000111011111110000101001100101101111110000011101110010000100010000101110010000111100...
result:
ok n=4000
Test #13:
score: 0
Accepted
time: 2803ms
memory: 443612kb
input:
4000 -+++---+-------+-++++-+++-++-+--++----++++++---+---++-++++-+++-++++-+---+--+++-----+-+--++-+--+-++++--+--++-+---+++++++++-+++++++-+++--+-+---++-+-++----+-++--++-++++++++++++++-+++-++-+++-++-++---+---+++-+-+++++++--+-+++-++-+-----+++-++--+++------+++--+++---+--+----++-+--+-+---+--+---+-+-+--++++...
output:
Yes 10001110111111101000010001001011001111000000111011100100001000100001011101100011111010110010110100001101100101110000000001000000010001101011100101001111010011001000000000000001000100100010010011101110001010000000110100010010111110001001100011111100011000111011011110010110101110110111010101100001...
result:
ok n=4000
Test #14:
score: -100
Time Limit Exceeded
input:
4000 +--+++++--++--+-+++-++-+-+-+-+--++------++++---+++-+-+--+------++-+--++-+-+++-----+-+++++-+------++++-++++-+--+------++--+++++-+-+--+-+++++++++++++++-+--+-+-+---+-+-+++++-++--+-+---++-++--+--+-+++-+-+++++-+--++-+----+++-++-++++-+---+--+-++-++-+-+-+---++-++-+-+----++-++++-----------+++--++++-++-...