QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#597774 | #7857. (-1,1)-Sumplete | 000226 | TL | 1265ms | 527024kb | C++17 | 4.4kb | 2024-09-28 18:46:05 | 2024-09-28 18:46:08 |
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));
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;
Rep(i,1,n){
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: 0ms
memory: 5856kb
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: 6116kb
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: 5920kb
input:
3 +-+ -++ ++- 1 0 2 2 2 -1
output:
No
result:
ok n=3
Test #4:
score: 0
Accepted
time: 1ms
memory: 5752kb
input:
1 - -1 1
output:
No
result:
ok n=1
Test #5:
score: 0
Accepted
time: 1ms
memory: 7784kb
input:
1 - 0 0
output:
Yes 0
result:
ok n=1
Test #6:
score: 0
Accepted
time: 0ms
memory: 5996kb
input:
20 +-------+-----+++-++ -+-++++----++-++-++- -+++--+---+--+-++--- -+++-+--+----++---+- +++-+-++++++-+-+---+ -++-----+----++++++- +-++--+++++-++-+---- +-+----+---+-+++--+- +++++-+++++----+--+- ------++++---+--++-- ++++--------++++--+- -+-+-++++-+-++-++--+ ---+-++---+-++-++--- +-++++-++----+-+++-- +-+...
output:
Yes 10001111000000101100 01000001000110100011 01000101111001001101 10111011011101100111 10011101111101010100 11111111010001111011 01010100000101010101 01010110110101110010 00001100000110010010 11110000001111001100 00000011111100001010 10110100010100011001 10010111010101011000 10111100111100100100 01...
result:
ok n=20
Test #7:
score: 0
Accepted
time: 0ms
memory: 8368kb
input:
100 ++++-+-+--++++++-+--+--++-+-+--+++++-+++---+-+-+-++-+-+++-------+-++--+-++--+--+++++-++-+---+--+--++ -++--++-+-++++-+---++-+-+-+-+-+-+-+-+--+-+--+--+++---+--+-----+-----+-++-++-+-++++++--+-+++-+++-++++ --+---++-++--++-+++-------+--+-++------+-----+--+----++++++++-+--+++++--++--+-+-+++---+--+++-+...
output:
Yes 1111010111000000101101111010100111110111000101010110101110000000101100101100100111100010101101011010 0110011111000010000110101010101010101001010010011100010010000010000010110110101111110110110101100000 0010000010011001000110000010010110000001000001001000011111111010011111001100101011100010010001...
result:
ok n=100
Test #8:
score: 0
Accepted
time: 8ms
memory: 17648kb
input:
500 --+-+-+-++-----+++--+-+++-+---+-+-------+++--++++++-+--++--+-+-++++-++++--++--+---++--++----++--+---++-++--+-----+-+---++-++++-+++++++---++-++--+-++++-+----++-+++-+++---+--+++-+--++-++--+++++++-+++--+---+---+-+---++-+-+--+-+++-++-----+++-++-+++-+-++--++++++-+-++-+++---++-+++-++----+--+++----++++...
output:
Yes 11100110000110001010000111101100110001110111000000101101100011001000101001111011001011111111000101011001100011101101000110101100011011000100011100010100010000000010111011111100110110101100000001000110111011101011100101011010001001111100010010001010011000000101001000111001000100111101100011110000...
result:
ok n=500
Test #9:
score: 0
Accepted
time: 1060ms
memory: 526608kb
input:
4000 -++-+-+-+--+-++++---+-++------++---+-+++--+++--+++++++---+-++-+++++++----+---+++-++--++---+-++--+----+---+--++-+-+-+-----+-+---++-++--+---+++-++++-+-----++--++-++---++-+--+++-+--+--+-+-++-+++--++---+++-+-+---+++-++-+-++-+-+++---+++---+-+--++---+-+---+--+++--+----+-+--++---+-----+-+--+----+-+++-...
output:
Yes 01101010100101111000101100000011000101110011100111111100010110111111100001000111011001100010110010000100001100101010111110101110010011011100010000101111100110010011100101100010110110101001000110011100010101110001001010010100011100011101011001110101110110001101111010110011101111101011011110100010...
result:
ok n=4000
Test #10:
score: 0
Accepted
time: 1180ms
memory: 525168kb
input:
4000 +---+--++-+--++-+-++--+++--++--+++-+-+-+--++++++-++-+-+++-+---++++-+-+++----++-+---++--++--+++-----++---++-+--++++----++--++--+-+-++--+--+++++-+---+++-+++--++++-++-+++++++----+++-----+--++-+++-++-++-+++-+--++++++-+--++--+-+---++--------+-+--++----+-++-+-++---+--++--+-+--+-+++-+--+--++++-++----+...
output:
Yes 10001001101001101011001110011001110101010011111101101011101000111101011100001101000110011001110000011000110100111100001100110010101100100111110100011101110011110110111111100001110000010011011101101101110100011111010011001010001100000000101001100001011010110001001100101001011101001001111011000010...
result:
ok n=4000
Test #11:
score: 0
Accepted
time: 989ms
memory: 527024kb
input:
4000 -+--+------+--+++-++-----++--+-++-++-++-+-+-++++++--++--+-++-+-+++---++-+-+++++-++++++-+-++-++-++-+-++---+-+-------++-+++-++-+-++++-++-+-+-----+----+--+----++++-------++-+--+++----+++++++-+--+-+---+-+++++-+-----++-------++++--+-+-++---++++-++++-++-+++-+-++---+--+---+-++++++--++---+-++++++-+-+--...
output:
Yes 01001000000100111011000001100101101101101010111111001100101101011100011010111110111111010110110110101100010100000001101110110101111011010100000100001001000011110000000110100111000011111110100101000101111101000001100000001111001010110010000100001001000101001110110111010000001100111010000001010111...
result:
ok n=4000
Test #12:
score: 0
Accepted
time: 1121ms
memory: 525608kb
input:
4000 +-+-----++++-----++++-+-++-+----+++---++--+---+++-+-++------+-+-++++----+-++++--+-++----+-+---+--+-----+-++--++-+++---+---+++---++-+++---++++---++----+++--+---+---+++-++-+-+-+--+++--++----++-+------+++-++-++--+--+++---+-------++++-+-++--++-+--+------+++++---+---++-++++-+++-++++-+---++-++++----+...
output:
Yes 10100000111100000111101011010000111000110010001110101100000010101111000010111100101100001010001001000001011001101110001000111000110111000111100011000011100100010001110110101010011100110000110100000011101101100100111000100000001111010110011010010000001111100010001101111011101111010001101111000011...
result:
ok n=4000
Test #13:
score: 0
Accepted
time: 1071ms
memory: 524928kb
input:
4000 -+++---+-------+-++++-+++-++-+--++----++++++---+---++-++++-+++-++++-+---+--+++-----+-+--++-+--+-++++--+--++-+---+++++++++-+++++++-+++--+-+---++-+-++----+-++--++-++++++++++++++-+++-++-+++-++-++---+---+++-+-+++++++--+-+++-++-+-----+++-++--+++------+++--+++---+--+----++-+--+-+---+--+---+-+-+--++++...
output:
Yes 01110001000000010111101110110100110000111111000100011011110111011110100010011100000101001101001011110010011010001111111110111111101110010100011010110000101100110111111111111110111011011101101100010001110101111111001011101101000001110110011100000011100111000100100001101001010001001000101010011110...
result:
ok n=4000
Test #14:
score: 0
Accepted
time: 1265ms
memory: 524972kb
input:
4000 +--+++++--++--+-+++-++-+-+-+-+--++------++++---+++-+-+--+------++-+--++-+-+++-----+-+++++-+------++++-++++-+--+------++--+++++-+-+--+-+++++++++++++++-+--+-+-+---+-+-+++++-++--+-+---++-++--+--+-+++-+-+++++-+--++-+----+++-++-++++-+---+--+-++-++-+-+-+---++-++-+-+----++-++++-----------+++--++++-++-...
output:
Yes 01100100000011010001101110111011101101111001111100000011011110100110101111001101110100000100100110000110000011011011100110010011001111000001000000010001011010110010101100100110101110000101110000011110000010111110111100010011011100100110101100111111110011111110101000101101011111011100001100000010...
result:
ok n=4000
Test #15:
score: 0
Accepted
time: 925ms
memory: 525076kb
input:
4000 ---++-++-+-+----++-++++-----------+++--++++-++-++--+-+--+--+-+-++++--++-++--+++++--++--+-+----+-+---++-+++-+--+-++++++++-++---++++-+--+-+++---+-+--+--+-+--+--++++++-+---++++++-++++----+-+-+-++--+---+--+-+++--++++++-+++-+---+--+-----------++-+++--+++++++--++-+++++--+++-+-+++++++++--+---+++--+-+-...
output:
Yes 00011011010100001101111000000000001110011110110110010100100101011110011011001111100110010100001010001101110100101111111101100011110100101110001010010010100100111111011110000001000011110101010011011101101000110000001000101110110111111111110010001100000001100100000110001010000000001101110001101011...
result:
ok n=4000
Test #16:
score: -100
Time Limit Exceeded
input:
4000 ++-+-------+--++-++-++--++-+++++-++++--+-----++-+--+---++++--+-----++++++---+--+---+------+++-+-----+-+++--+++-+-+-+++-----++---+-+---+-+++++-+--+-++--++-+-----++-+-+---+++-+----++++---++--+-+-++-++-+--++---+++------++-+-++++--+--++-++-+++-++-+--++----++---+-+++-+-+++-++-+--++-++++--++-+-+-+-+-...