QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#597786 | #7857. (-1,1)-Sumplete | 000226 | TL | 1ms | 7852kb | C++17 | 4.6kb | 2024-09-28 18:48:13 | 2024-09-28 18:48:15 |
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;
class Input {
#define MX 1000000
private :
char buf[MX], *p1 = buf, *p2 = buf;
inline char gc() {
if(p1 == p2) p2 = (p1 = buf) + fread(buf, 1, MX, stdin);
return p1 == p2 ? EOF : *(p1 ++);
}
public :
Input() {
#ifdef Open_File
freopen("a.in", "r", stdin);
freopen("a.out", "w", stdout);
#endif
}
template <typename T>
inline Input& operator >>(T &x) {
x = 0; int f = 1; char a = gc();
for(; ! isdigit(a); a = gc()) if(a == '-') f = -1;
for(; isdigit(a); a = gc())
x = x * 10 + a - '0';
x *= f;
return *this;
}
inline Input& operator >>(char &ch) {
while(1) {
ch = gc();
if(ch != '\n' && ch != ' ') return *this;
}
}
inline Input& operator >>(char *s) {
int p = 0;
while(1) {
s[p] = gc();
if(s[p] == '\n' || s[p] == ' ' || s[p] == EOF) break;
p ++;
}
s[p] = '\0';
return *this;
}
#undef MX
} Fin;
class Output {
#define MX 1000000
private :
char ouf[MX], *p1 = ouf, *p2 = ouf;
char Of[105], *o1 = Of, *o2 = Of;
void flush() { fwrite(ouf, 1, p2 - p1, stdout); p2 = p1; }
inline void pc(char ch) {
* (p2 ++) = ch;
if(p2 == p1 + MX) flush();
}
public :
template <typename T>
inline Output& operator << (T n) {
if(n < 0) pc('-'), n = -n;
if(n == 0) pc('0');
while(n) *(o1 ++) = (n % 10) ^ 48, n /= 10;
while(o1 != o2) pc(* (--o1));
return *this;
}
inline Output & operator << (char ch) {
pc(ch); return *this;
}
inline Output & operator <<(const char *ch) {
const char *p = ch;
while( *p != '\0' ) pc(* p ++);
return * this;
}
~Output() { flush(); }
#undef MX
} Fout;
#define cin Fin
#define cout Fout
#define endl '\n'
int n;
bool a[maxn][maxn];
char s[maxn];
int R[maxn],C[maxn],sR[maxn],sC[maxn];
int S,T;
ll read() {
ll x=0, f=1; char ch=' ';
while(!isdigit(ch)) { ch=getchar(); if(ch=='-') f=-1; }
while(isdigit(ch)) x=(x<<3)+(x<<1)+(ch-48), ch=getchar();
return x*f;
}
struct Dinic{
struct Edge{
int to, cap, flow;
};
vector<Edge> edges;
vector<int> G[maxn*2];
bool vis[maxn*2];
int m, s, t, d[maxn*2], cur[maxn*2];
void charu(int from, int to, int cap) {
edges.push_back({to, cap, 0});
edges.push_back({from, 0, 0});
int m=edges.size();
G[from].push_back(m-2);
G[to].push_back(m-1);
}
bool bfs() {
//memset(vis, 0, sizeof(vis));
for (int i = 1; i <= n * 2 + 2; i ++) vis[i] = 0;
queue<int> q;
q.push(s), d[s]=0, vis[s]=1;
while(!q.empty()) {
int u=q.front(); q.pop();
for(int id:G[u]) {
Edge &e=edges[id];
if(!vis[e.to]&&e.cap>e.flow) {
q.push(e.to);
vis[e.to]=1;
d[e.to]=d[u]+1;
}
}
}
return vis[t];
}
int dfs(int u, int a) {
if(u==t||a==0) return a;
int flow=0, f;
for(int &i=cur[u];i<G[u].size();i++) {
Edge &e=edges[G[u][i]];
if(d[u]+1==d[e.to]&&(f=dfs(e.to,min(a,e.cap-e.flow)))>0) {
e.flow+=f;
edges[G[u][i]^1].flow-=f;
flow+=f;
a-=f;
if(!a) break;
}
}
return flow;
}
ll solve(int _s, int _t) {
s=_s, t=_t; ll flow=0;
while(bfs()) {
//memset(cur, 0, sizeof(cur));
flow+=dfs(s, INF);
}
return flow;
}
void Build(){
Rep(u,1,n) {
for(int id:G[u]) {
Edge e=edges[id];
if(e.to!=s) {
int v=e.to-n;
if(e.cap==e.flow) a[u][v]^=1;
}
}
}
}
}tnt;
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;
static int seq[maxn];
for (int i = 1; i <= n; i ++) seq[i] = i;
random_shuffle(seq + 1, seq + 1 + n);
Rep(x,1,n){
int i = seq[x];
tnt.charu(S,i,sR[i]-R[i]);
tnt.charu(i+n,T,sC[i]-C[i]);
sum+=sR[i]-R[i];
sam+=sC[i]-C[i];
}
if(sum!=sam)return cout<<"No\n",void();
Rep(i,1,n)Rep(j,1,n) tnt.charu(i,j+n,1);
int res=tnt.solve(S,T);
if(res!=sum)return cout<<"No\n",void();
tnt.Build();
cout<<"Yes\n";
Rep(i,1,n){
Rep(j,1,n)cout<<a[i][j];
cout<<"\n";
}
}
int main (){ return solve(),0; }
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 1ms
memory: 7852kb
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: 5844kb
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: 5952kb
input:
3 +-+ -++ ++- 1 0 2 2 2 -1
output:
No
result:
ok n=3
Test #4:
score: 0
Accepted
time: 1ms
memory: 6072kb
input:
1 - -1 1
output:
No
result:
ok n=1
Test #5:
score: 0
Accepted
time: 1ms
memory: 5816kb
input:
1 - 0 0
output:
Yes 0
result:
ok n=1
Test #6:
score: -100
Time Limit Exceeded
input:
20 +-------+-----+++-++ -+-++++----++-++-++- -+++--+---+--+-++--- -+++-+--+----++---+- +++-+-++++++-+-+---+ -++-----+----++++++- +-++--+++++-++-+---- +-+----+---+-+++--+- +++++-+++++----+--+- ------++++---+--++-- ++++--------++++--+- -+-+-++++-+-++-++--+ ---+-++---+-++-++--- +-++++-++----+-+++-- +-+...