QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#289795#7857. (-1,1)-Sumpleteucup-team139#TL 40ms12412kbC++235.6kb2023-12-24 00:43:202023-12-24 00:43:21

Judging History

你现在查看的是最新测评结果

  • [2023-12-24 00:43:21]
  • 评测
  • 测评结果:TL
  • 用时:40ms
  • 内存:12412kb
  • [2023-12-24 00:43:20]
  • 提交

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
-++-+-+-+--+-++++---+-++------++---+-+++--+++--+++++++---+-++-+++++++----+---+++-++--++---+-++--+----+---+--++-+-+-+-----+-+---++-++--+---+++-++++-+-----++--++-++---++-+--+++-+--+--+-+-++-+++--++---+++-+-+---+++-++-+-++-+-+++---+++---+-+--++---+-+---+--+++--+----+-+--++---+-----+-+--+----+-+++-...

output:


result: