QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#424660 | #7857. (-1,1)-Sumplete | lmeowdn# | TL | 55ms | 15828kb | C++14 | 2.8kb | 2024-05-29 15:10:21 | 2024-05-29 15:10:22 |
Judging History
answer
//Shirasu Azusa 2024.5
#include <bits/stdc++.h>
#define fi first
#define se second
#define eb emplace_back
#define mp make_pair
using namespace std;
typedef long double ld;
typedef long long ll;
typedef unsigned long long ull;
typedef __int128 i128;
template<class T,class S>
bool chmax(T &a,const S b) {return (a<b?a=b,1:0);}
template<class T,class S>
bool chmin(T &a,const S b) {return (a>b?a=b,1:0);}
int popcnt(int x) {return __builtin_popcount(x);}
int popcnt(ll x) {return __builtin_popcountll(x);}
int topbit(int x) {return (x==0?-1:31-__builtin_clz(x));}
int topbit(ll x) {return (x==0?-1:63-__builtin_clzll(x));}
int lowbit(int x) {return (x==0?-1:__builtin_ctz(x));}
int lowbit(ll x) {return (x==0?-1:__builtin_ctzll(x));}
#define int long long
#define rep(i,a,b) for(int i=(a);i<=(b);i++)
#define per(i,a,b) for(int i=(a);i>=(b);i--)
typedef pair<int,int> pii;
typedef vector<int> vi;
typedef vector<pii> vp;
typedef tuple<int,int,int> tiii;
int read() {
int x=0,w=1; char c=getchar();
while(!isdigit(c)) {if(c=='-') w=-1; c=getchar();}
while(isdigit(c)) {x=x*10+(c-'0'); c=getchar();}
return x*w;
}
const int N=1e4+5,M=3.5e7+5,inf=(1ll<<31)-1;
int n;
char s[N];
namespace NetF {
int n,m,s,t,d[N];
struct edge {int to,nxt,c;} e[M]; int hd[N],cur[N],tot=1;
void add(int u,int v,int c) {e[++tot]=(edge){v,hd[u],c}; hd[u]=tot;}
void addh(int u,int v,int c) {add(u,v,c), add(v,u,0);}
bool bfs() {
queue<int>q; q.push(s); rep(i,1,n) d[i]=N+1; d[s]=0;
while(!q.empty()) {
int u=q.front(); q.pop();
for(int i=hd[u],v;i;i=e[i].nxt)
if(e[i].c&&d[v=e[i].to]==N+1) {d[v]=d[u]+1; if(v==t) return 1; q.push(v);}
} return 0;
}
int dfs(int u,int flow) {
int rest=flow; if(u==t) return flow;
for(int i=cur[u],v;i&&rest;i=e[i].nxt) {
if(d[v=e[i].to]!=d[u]+1||!e[i].c) continue;
cur[u]=i; int use=dfs(v,min(rest,e[i].c));
if(!use) d[v]=0;
e[i].c-=use, rest-=use, e[i^1].c+=use;
} return flow-rest;
}
int flow(int S,int T,int ans=0) {
n=T, s=S, t=T;
while(bfs()) {
rep(i,1,n) cur[i]=hd[i]; int res=0;
while(res=dfs(s,inf)) ans+=res;
} return ans;
}
}
signed main() {
n=read();
rep(i,1,n) {
scanf("%s",s+1);
rep(j,1,n) {
if(s[j]=='+') NetF::addh(i,j+n,1);
else NetF::addh(j+n,i,1);
}
}
int S=n*2+1, T=n*2+2, sum1=0, sum2=0, pr=0;
rep(i,1,n) {
int x=read();
if(x>0) NetF::addh(S,i,x), sum1+=x, pr+=x;
else NetF::addh(i,T,-x), sum1+=x;
}
rep(i,1,n) {
int x=read();
if(x>0) NetF::addh(i+n,T,x), sum2+=x;
else NetF::addh(S,i+n,-x), sum2+=x, pr-=x;
}
if(sum1!=sum2) return puts("No"), 0;
int x=NetF::flow(S,T);
if(x!=pr) return puts("No"), 0;
puts("Yes"); int tt=0;
rep(i,1,n) {
rep(j,1,n) {
if(NetF::e[(++tt)*2].c==0) putchar('1');
else putchar('0');
} puts("");
}
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 3780kb
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: 3656kb
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: 3980kb
input:
3 +-+ -++ ++- 1 0 2 2 2 -1
output:
No
result:
ok n=3
Test #4:
score: 0
Accepted
time: 1ms
memory: 3696kb
input:
1 - -1 1
output:
No
result:
ok n=1
Test #5:
score: 0
Accepted
time: 0ms
memory: 3648kb
input:
1 - 0 0
output:
Yes 0
result:
ok n=1
Test #6:
score: 0
Accepted
time: 1ms
memory: 3728kb
input:
20 +-------+-----+++-++ -+-++++----++-++-++- -+++--+---+--+-++--- -+++-+--+----++---+- +++-+-++++++-+-+---+ -++-----+----++++++- +-++--+++++-++-+---- +-+----+---+-+++--+- +++++-+++++----+--+- ------++++---+--++-- ++++--------++++--+- -+-+-++++-+-++-++--+ ---+-++---+-++-++--- +-++++-++----+-+++-- +-+...
output:
Yes 00000000010000000100 00000000000010100010 00000000010000000100 00000011010000000100 00100000100101010001 00000000010000000000 00000000000101000101 00000000000000000001 00000000000000000000 00000100001100000001 00000001011100000101 00000000000101001000 10000000000001011000 00000000000001011000 00...
result:
ok n=20
Test #7:
score: 0
Accepted
time: 2ms
memory: 4120kb
input:
100 ++++-+-+--++++++-+--+--++-+-+--+++++-+++---+-+-+-++-+-+++-------+-++--+-++--+--+++++-++-+---+--+--++ -++--++-+-++++-+---++-+-+-+-+-+-+-+-+--+-+--+--+++---+--+-----+-----+-++-++-+-++++++--+-+++-+++-++++ --+---++-++--++-+++-------+--+-++------+-----+--+----++++++++-+--+++++--++--+-+-+++---+--+++-+...
output:
Yes 1111010100111111010010011010100010100000000000000000000000000000000000000000000011110110100010010011 0110011010111101000110101010100010100000000000000000000000000000000000000000101111110010111011101111 0010001101100110111000000010010010000000000000000000000000000000000000000000001011100010011101...
result:
ok n=100
Test #8:
score: 0
Accepted
time: 55ms
memory: 15828kb
input:
500 --+-+-+-++-----+++--+-+++-+---+-+-------+++--++++++-+--++--+-+-++++-++++--++--+---++--++----++--+---++-++--+-----+-+---++-++++-+++++++---++-++--+-++++-+----++-+++-+++---+--+++-+--++-++--+++++++-+++--+---+---+-+---++-+-+--+-+++-++-----+++-++-+++-+-++--++++++-+-++-+++---++-+++-++----+--+++----++++...
output:
Yes 11010101001111100011010001011101011111110001100000010110011010100001000011001101110011001111001101110010011011111010111001000010000000111001001101000010111100100010001110110001010001001100000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000...
result:
ok n=500
Test #9:
score: -100
Time Limit Exceeded
input:
4000 -++-+-+-+--+-++++---+-++------++---+-+++--+++--+++++++---+-++-+++++++----+---+++-++--++---+-++--+----+---+--++-+-+-+-----+-+---++-++--+---+++-++++-+-----++--++-++---++-+--+++-+--+--+-+-++-+++--++---+++-+-+---+++-++-+-++-+-+++---+++---+-+--++---+-+---+--+++--+----+-+--++---+-----+-+--+----+-+++-...