QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#289795 | #7857. (-1,1)-Sumplete | ucup-team139# | TL | 40ms | 12412kb | C++23 | 5.6kb | 2023-12-24 00:43:20 | 2023-12-24 00:43:21 |
Judging History
answer
#pragma GCC optimize("O3")
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
using db = long double; // or double if tight TL
using str = string;
using pi = pair<int,int>;
#define mp make_pair
#define f first
#define s second
#define tcT template<class T
tcT> using V = vector<T>;
tcT, size_t SZ> using AR = array<T,SZ>;
using vi = V<int>;
using vb = V<bool>;
using vpi = V<pi>;
#define sz(x) int((x).size())
#define all(x) begin(x), end(x)
#define sor(x) sort(all(x))
#define rsz resize
#define pb push_back
#define ft front()
#define bk back()
#define FOR(i,a,b) for (int i = (a); i < (b); ++i)
#define F0R(i,a) FOR(i,0,a)
#define ROF(i,a,b) for (int i = (b)-1; i >= (a); --i)
#define R0F(i,a) ROF(i,0,a)
#define rep(a) F0R(_,a)
#define each(a,x) for (auto& a: x)
const int MOD = 1e9+7;
const db PI = acos((db)-1);
mt19937 rng(0); // or mt19937_64
tcT> bool ckmin(T& a, const T& b) {
return b < a ? a = b, 1 : 0; } // set a = min(a,b)
tcT> bool ckmax(T& a, const T& b) {
return a < b ? a = b, 1 : 0; } // set a = max(a,b)
template <int SZ> struct HLPP {
typedef ll F; // flow type
struct Edge { int to, rev; F f; };
const F INF = numeric_limits<F>::max();
int N,s,t;
V<Edge> adj[SZ];
void ae(int u, int v, F cap) {
assert(cap >= 0); // don't try smth dumb
Edge a{v, sz(adj[v]), cap}, b{u, sz(adj[u]), 0};
adj[u].pb(a), adj[v].pb(b);
}
vi lst[SZ], gap[SZ];
F excess[SZ];
int highest, height[SZ], cnt[SZ], work;
void updHeight(int v, int nh) {
work++;
if (height[v] != N) cnt[height[v]]--;
height[v] = nh;
if (nh == N) return;
cnt[nh]++, highest = nh;
gap[nh].pb(v);
if (excess[v] > 0) lst[nh].pb(v);
}
void globalRelabel() {
work = 0;
F0R(i,N) height[i] = N, cnt[i] = 0;
F0R(i,highest) lst[i].clear(), gap[i].clear();
height[t] = 0;
queue<int> q({t});
while (sz(q)) {
int v = q.ft; q.pop();
each(e,adj[v])
if (height[e.to] == N && adj[e.to][e.rev].f > 0)
q.push(e.to), updHeight(e.to, height[v] + 1);
highest = height[v];
}
}
void push(int v, Edge& e) {
if (excess[e.to] == 0) lst[height[e.to]].pb(e.to);
F df = min(excess[v], e.f);
e.f -= df, adj[e.to][e.rev].f += df;
excess[v] -= df, excess[e.to] += df;
}
void discharge(int v) {
int nh = N;
each(e,adj[v]) {
if (e.f > 0) {
if (height[v] == height[e.to] + 1) {
push(v, e);
if (excess[v] <= 0) return;
} else ckmin(nh,height[e.to]+1);
}
}
if (cnt[height[v]] > 1) updHeight(v, nh);
else {
FOR(i,height[v],highest+1) {
each(j,gap[i]) updHeight(j, N);
gap[i].clear();
}
}
}
F maxFlow(int _N, int _s, int _t) {
N = _N, s = _s, t = _t; if (s == t) return -1;
F0R(i,N) excess[i] = 0;
excess[s] = INF, excess[t] = -INF;
globalRelabel();
each(e,adj[s]) push(s,e);
for (; highest >= 0; highest--)
while (sz(lst[highest])) {
int v = lst[highest].bk;
lst[highest].pop_back();
discharge(v);
if (work > 4*N) globalRelabel();
}
return excess[t]+INF;
}
};
void solve(int t){
int n;
cin>>n;
vector mat(n,vector(n,'.'));
for(int i=0;i<n;i++){
for(int j=0;j<n;j++){
cin>>mat[i][j];
}
}
vector r(n,0),c(n,0);
for(int i=0;i<n;i++)cin>>r[i];
for(int i=0;i<n;i++)cin>>c[i];
for(int i=0;i<n;i++){
for(int j=0;j<n;j++){
if(mat[i][j]=='-'){
r[i]++;
c[j]++;
}
}
}
long long totr=0,totc=0;
for(int i=0;i<n;i++){
if(r[i]<0 || c[i]<0){
cout<<"No\n";
return;
}
totr+=r[i];
totc+=c[i];
}
if(totr!=totc){
cout<<"No\n";
}else{
HLPP<8002> ds;
int source = 2*n;
int sink = 2*n+1;
//ds.init(2*n+2);
for(int i=0;i<n;i++){
ds.ae(source,i,r[i]);
ds.ae(n+i,sink,c[i]);
}
for(int i=0;i<n;i++){
for(int j=0;j<n;j++){
ds.ae(i,n+j,1);
}
}
if(ds.maxFlow(8002,source,sink)!=totr){
cout<<"No\n";
}else{
vector ok(n,vector(n,false));
for(int i=0;i<n;i++){
for(auto j : ds.adj[i]){
if(j.to>=n && j.f==0){
ok[i][j.to-n]=true;
}
}
}
cout<<"Yes\n";
for(int i=0;i<n;i++){
string tmp;
tmp.resize(n);
for(int j=0;j<n;j++){
if(ok[i][j]^(mat[i][j]=='+')){
tmp[j]='0';
}else{
tmp[j]='1';
}
}
cout<<tmp<<"\n";
}
}
}
}
int main(){
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int t=1;
//cin>>t;
for(int i=1;i<=t;i++)solve(i);
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 1ms
memory: 4148kb
input:
3 +-+ -++ +-+ 1 1 1 1 -1 3
output:
Yes 111 001 001
result:
ok n=3
Test #2:
score: 0
Accepted
time: 0ms
memory: 4180kb
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: 4136kb
input:
3 +-+ -++ ++- 1 0 2 2 2 -1
output:
No
result:
ok n=3
Test #4:
score: 0
Accepted
time: 1ms
memory: 4188kb
input:
1 - -1 1
output:
No
result:
ok n=1
Test #5:
score: 0
Accepted
time: 1ms
memory: 4140kb
input:
1 - 0 0
output:
Yes 0
result:
ok n=1
Test #6:
score: 0
Accepted
time: 0ms
memory: 4188kb
input:
20 +-------+-----+++-++ -+-++++----++-++-++- -+++--+---+--+-++--- -+++-+--+----++---+- +++-+-++++++-+-+---+ -++-----+----++++++- +-++--+++++-++-+---- +-+----+---+-+++--+- +++++-+++++----+--+- ------++++---+--++-- ++++--------++++--+- -+-+-++++-+-++-++--+ ---+-++---+-++-++--- +-++++-++----+-+++-- +-+...
output:
Yes 10011111011100111011 01000001110010110110 01001101111011001000 01001011011011010010 11110100001101010001 01011111010000111010 11001100000110011000 01010110000100111010 00001000000000011111 11110000101001000001 00000111111111100101 10110110110011101110 11110111001011011101 01011100100001001011 01...
result:
ok n=20
Test #7:
score: 0
Accepted
time: 0ms
memory: 4492kb
input:
100 ++++-+-+--++++++-+--+--++-+-+--+++++-+++---+-+-+-++-+-+++-------+-++--+-++--+--+++++-++-+---+--+--++ -++--++-+-++++-+---++-+-+-+-+-+-+-+-+--+-+--+--+++---+--+-----+-----+-++-++-+-++++++--+-+++-+++-++++ --+---++-++--++-+++-------+--+-++------+-----+--+----++++++++-+--+++++--++--+-+-+++---+--+++-+...
output:
Yes 1111010100111111010010011010100111110111000101010110101101111111010011010011011111110110100010010011 0110011010111101000110101010101010101001010010011100010010001101111101001001101111110010111011101111 0010001101100110111000000010010110000001000001001000011000000101100000110011101011100010011101...
result:
ok n=100
Test #8:
score: 0
Accepted
time: 40ms
memory: 12412kb
input:
500 --+-+-+-++-----+++--+-+++-+---+-+-------+++--++++++-+--++--+-+-++++-++++--++--+---++--++----++--+---++-++--+-----+-+---++-++++-+++++++---++-++--+-++++-+----++-+++-+++---+--+++-+--++-++--+++++++-+++--+---+---+-+---++-+-+--+-+++-++-----+++-++-+++-+-++--++++++-+-++-+++---++-+++-++----+--+++----++++...
output:
Yes 00101010110000010011010001011101011111110001100000010110011010100001000011001101110011001111001101110010011011111010111001000010000000111001001101000010111100100010001110110001011001001100000001000110111011101011100101011010001001111100010010001010011000000101001000111001000100111101100011110000...
result:
ok n=500
Test #9:
score: -100
Time Limit Exceeded
input:
4000 -++-+-+-+--+-++++---+-++------++---+-+++--+++--+++++++---+-++-+++++++----+---+++-++--++---+-++--+----+---+--++-+-+-+-----+-+---++-++--+---+++-++++-+-----++--++-++---++-+--+++-+--+--+-+-++-+++--++---+++-+-+---+++-++-+-++-+-+++---+++---+-+--++---+-+---+--+++--+----+-+--++---+-----+-+--+----+-+++-...