QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#289827#7857. (-1,1)-Sumpleteucup-team139WA 1449ms595608kbC++237.1kb2023-12-24 02:10:422023-12-24 02:10:43

Judging History

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

  • [2023-12-24 02:10:43]
  • 评测
  • 测评结果:WA
  • 用时:1449ms
  • 内存:595608kb
  • [2023-12-24 02:10:42]
  • 提交

answer

#pragma GCC optimize("O3")
#include<bits/stdc++.h>
using namespace std;

using pi = pair<int,int>;
#define sz(x) int((x).size())
template<class F> struct Dinic {
    struct Edge { int to, rev; F cap; };
    int N; vector<vector<Edge>> adj;
    void init(int _N) { N = _N; adj.resize(N); 
        //for(int i=0;i<N;i++)adj[i].reserve(N+2);
    } //0-based
    void ae(int a, int b, F cap, F rcap = 0) {
        //assert(min(cap,rcap) >= 0); // saved me > once
        adj[a].push_back({b,sz(adj[b]),cap});
        adj[b].push_back({a,sz(adj[a])-1,rcap});
        //return {a,sz(adj[a])-1};
    }
    F edgeFlow(pi loc) { // get flow along original edge
        const Edge& e = adj.at(loc.first).at(loc.second);
        return adj.at(e.to).at(e.rev).cap;
    }
    vector<int> lev, ptr;
    bool bfs(int s,int t){//level=shortest dist from source
        lev = ptr = vector<int>(N);
        lev[s] = 1; queue<int> q({s});
        while (sz(q)) { int u = q.front(); q.pop();
            for(auto& e: adj[u]) if (e.cap && !lev[e.to]) {
                q.push(e.to), lev[e.to] = lev[u]+1;
                if (e.to == t) return 1;
            }
        }
        return 0;
    }
    F dfs(int v, int t, F flo) {
        if (v == t) return flo;
        for (int& i = ptr[v]; i < sz(adj[v]); i++) {
            Edge& e = adj[v][i];
            if (lev[e.to]!=lev[v]+1||!e.cap) continue;
            if (F df = dfs(e.to,t,min(flo,e.cap))) {
                e.cap -= df; adj[e.to][e.rev].cap += df;
                return df; } // saturated $\geq1$ one edge
        }
        return 0;
    }
    F maxFlow(int s, int t,int ttt) {
        F tot = 0; while (bfs(s,t)) while (F df =
            dfs(s,t,numeric_limits<F>::max())) {
            tot += df;
        }
        return tot;
    }
};

void solve(int t){
    int n;
    cin>>n;
    //n=2000;
    
    vector mat(n,vector(n,'.'));
    for(int i=0;i<n;i++){
        for(int j=0;j<n;j++){
            cin>>mat[i][j];
            //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 || r[i]>n || c[i]>n){
            cout<<"No\n";
            return;
        }
        totr+=r[i];
        totc+=c[i];
    }
    
    if(totr!=totc){
        cout<<"No\n";
    }else{
        vector ok(n,vector<int>(n,-1));
        vector<int> dispr(n,n), dispc(n,n);
        
        queue<pair<int,int>> gg;
        for(int i=0;i<n;i++){
            if(r[i]==0 || r[i]==n){
                gg.push({i,0});
            }
            if(c[i]==0 || c[i]==n){
                gg.push({i,1});
            }
        }
        
        vector<bool> okr(n,false),okc(n,false);
        while(n>1200 && !gg.empty()){
            
            auto [x,y] = gg.front();
            gg.pop();
            //cout<<"fixo "<<x<<" "<<(y==0 ? "colonna" : "riga")<<"\n";
            
            if(y==0){
                okr[x]=true;
                if(r[x]==0){
                    for(int i=0;i<n;i++){
                        if(ok[x][i]==-1){
                            ok[x][i]=0;
                            dispc[i]--;
                            if(dispc[i]==c[i]){
                                gg.push({i,1});
                            }
                            if(dispc[i]<c[i]){
                                cout<<"No\n";
                                return;
                            }
                        }
                    }
                }else{
r[x]=0;
                    totr-=r[x];
                    for(int i=0;i<n;i++){
                        if(ok[x][i]==-1){
                            ok[x][i]=1;
                            c[i]--;
                            dispc[i]--;
                            if(c[i]==0){
                                gg.push({i,1});
                            }
                            if(c[i]<0){
                                cout<<"No\n";
                                return;
                            }
                        }
                    }
                }
            }else{
                okc[x]=true;
                if(c[x]==0){
                    for(int i=0;i<n;i++){
                        if(ok[i][x]==-1){
                            ok[i][x]=0;
                            dispr[i]--;
                            if(dispr[i]==r[i]){
                                gg.push({i,0});
                            }
                            if(dispr[i]<r[i]){
                                cout<<"No\n";
                                return;
                            }
                        }
                    }
                }else{
c[x]=0;
                    for(int i=0;i<n;i++){
                        if(ok[i][x]==-1){
                            ok[i][x]=1;
                            r[i]--;
                            dispr[i]--;
                            totr--;
                            if(r[i]==0){
                                gg.push({i,0});
                            }
                            if(r[i]<0){
                                cout<<"No\n";
                                return;
                            }
                        }
                    }
                }
            }
        }
        
        Dinic<long long> ds;
        int source = 2*n;
        int sink = 2*n+1;
        ds.init(2*n+2);
        
        for(int i=0;i<n;i++){
            //if(okr[i]==false)
            ds.ae(source,i,r[i]);
            //if(okc[i]==false)
            ds.ae(n+i,sink,c[i]);
        }
        
        for(int i=0;i<n;i++){
            for(int j=0;j<n;j++){
                if(ok[i][j]==-1){
                    ds.ae(i,n+j,1);
                    ok[i][j]=0;
                }
                
            }
        }
        
        if(ds.maxFlow(source,sink,totr)!=totr){
            cout<<"No\n";
        }else{
            for(int i=0;i<n;i++){
                for(auto j : ds.adj[i]){
                    if(j.to>=n && j.cap==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: 0ms
memory: 3568kb

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: 3568kb

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: 3808kb

input:

3
+-+
-++
++-
1 0 2
2 2 -1

output:

No

result:

ok n=3

Test #4:

score: 0
Accepted
time: 0ms
memory: 3836kb

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: 0ms
memory: 3868kb

input:

20
+-------+-----+++-++
-+-++++----++-++-++-
-+++--+---+--+-++---
-+++-+--+----++---+-
+++-+-++++++-+-+---+
-++-----+----++++++-
+-++--+++++-++-+----
+-+----+---+-+++--+-
+++++-+++++----+--+-
------++++---+--++--
++++--------++++--+-
-+-+-++++-+-++-++--+
---+-++---+-++-++---
+-++++-++----+-+++--
+-+...

output:

Yes
01111000100100101110
10101110000100100011
10000010000111101100
10010100011111010111
00101011111100100100
11100001100110001001
00110010000100101101
00100000000100001101
00011000111001101101
11110000100001000011
00000011010000001101
10100000110011011010
00010001110011011000
10100010011001011100
01...

result:

ok n=20

Test #7:

score: 0
Accepted
time: 1ms
memory: 3940kb

input:

100
++++-+-+--++++++-+--+--++-+-+--+++++-+++---+-+-+-++-+-+++-------+-++--+-++--+--+++++-++-+---+--+--++
-++--++-+-++++-+---++-+-+-+-+-+-+-+-+--+-+--+--+++---+--+-----+-----+-++-++-+-++++++--+-+++-+++-++++
--+---++-++--++-+++-------+--+-++------+-----+--+----++++++++-+--+++++--++--+-+-+++---+--+++-+...

output:

Yes
0110001011100010101101100110100111110111000101010110101110000000101100101100111111110110100010010011
0111001110100000011001010110101010101001010010011100010010000010000010110110101111110010111011101111
1011010010111011011000000001101011110001000001001000011111111010011111001100101011100010011101...

result:

ok n=100

Test #8:

score: 0
Accepted
time: 15ms
memory: 12584kb

input:

500
--+-+-+-++-----+++--+-+++-+---+-+-------+++--++++++-+--++--+-+-++++-++++--++--+---++--++----++--+---++-++--+-----+-+---++-++++-+++++++---++-++--+-++++-+----++-+++-+++---+--+++-+--++-++--+++++++-+++--+---+---+-+---++-+-+--+-+++-++-----+++-++-+++-+-++--++++++-+-++-+++---++-+++-++----+--+++----++++...

output:

Yes
11010101001111100011010001011101011111110001100111101001100101011110111100110010001100110000110010010010011011111010111001000010000000111001001101000010111100100010001110110001011001001100000001000110111011101011100101011010001001111100010010001010011000000101001000111001000100111101100011110000...

result:

ok n=500

Test #9:

score: 0
Accepted
time: 1044ms
memory: 595480kb

input:

4000
-++-+-+-+--+-++++---+-++------++---+-+++--+++--+++++++---+-++-+++++++----+---+++-++--++---+-++--+----+---+--++-+-+-+-----+-+---++-++--+---+++-++++-+-----++--++-++---++-+--+++-+--+--+-+-++-+++--++---+++-+-+---+++-++-+-++-+-+++---+++---+-+--++---+-+---+--+++--+----+-+--++---+-----+-+--+----+-+++-...

output:

Yes
10010101011010000111010011111100111010001100011000000011101001000000011110111000100110011101001101111011101011010101000001010001101100100011101111010000011001101100011010011101001001010110111001100011101010001110110101101011100011100010100110001010001001110010000101001100010000010100100001011101...

result:

ok n=4000

Test #10:

score: 0
Accepted
time: 922ms
memory: 595480kb

input:

4000
+---+--++-+--++-+-++--+++--++--+++-+-+-+--++++++-++-+-+++-+---++++-+-+++----++-+---++--++--+++-----++---++-+--++++----++--++--+-+-++--+--+++++-+---+++-+++--++++-++-+++++++----+++-----+--++-+++-++-++-+++-+--++++++-+--++--+-+---++--------+-+--++----+-++-+-++---+--++--+-+--+-+++-+--+--++++-++----+...

output:

Yes
01110110010110010100110001100110001010101100000010010100010111000010100011110010111001100110001111100111001011000011110011001101010011011000001011100010001100001001000000011110001111101100100010010010001011000000101100110101110011111111010110011111011010110001001100101001011101001001111011000010...

result:

ok n=4000

Test #11:

score: 0
Accepted
time: 1229ms
memory: 595456kb

input:

4000
-+--+------+--+++-++-----++--+-++-++-++-+-+-++++++--++--+-++-+-+++---++-+-+++++-++++++-+-++-++-++-+-++---+-+-------++-+++-++-+-++++-++-+-+-----+----+--+----++++-------++-+--+++----+++++++-+--+-+---+-+++++-+-----++-------++++--+-+-++---++++-++++-++-+++-+-++---+--+---+-++++++--++---+-++++++-+-+--...

output:

Yes
10110111111011000100111110011010010010010101000000110011010010100011100101000001000000101001001001010011101011111110010001001010000100101011111011110110111100001111111001011000111100000001011010111010000010111110011111110000110101001110000100001001000101001110110111010000001100111010000001010111...

result:

ok n=4000

Test #12:

score: 0
Accepted
time: 958ms
memory: 595476kb

input:

4000
+-+-----++++-----++++-+-++-+----+++---++--+---+++-+-++------+-+-++++----+-++++--+-++----+-+---+--+-----+-++--++-+++---+---+++---++-+++---++++---++----+++--+---+---+++-++-+-+-+--+++--++----++-+------+++-++-++--+--+++---+-------++++-+-++--++-+--+------+++++---+---++-++++-+++-++++-+---++-++++----+...

output:

Yes
01011111000011111000010100101111000111001101110001010011111101010000111101000011010011110101110110111110100110010001110111000111001000111000011100111100011011101110001001010101100011001111001011111100010010011011000111011111110000101001100101101111110000011101110010000100010000101110010000111100...

result:

ok n=4000

Test #13:

score: 0
Accepted
time: 1135ms
memory: 595608kb

input:

4000
-+++---+-------+-++++-+++-++-+--++----++++++---+---++-++++-+++-++++-+---+--+++-----+-+--++-+--+-++++--+--++-+---+++++++++-+++++++-+++--+-+---++-+-++----+-++--++-++++++++++++++-+++-++-+++-++-++---+---+++-+-+++++++--+-+++-++-+-----+++-++--+++------+++--+++---+--+----++-+--+-+---+--+---+-+-+--++++...

output:

Yes
10001110111111101000010001001011001111000000111011100100001000100001011101100011111010110010110100001101100101110000000001000000010001101011100101001111010011001000000000000001000100100010010011101110001010000000110100010010111110001001100011111100011000111011011110010110101110110111010101100001...

result:

ok n=4000

Test #14:

score: 0
Accepted
time: 763ms
memory: 595536kb

input:

4000
+--+++++--++--+-+++-++-+-+-+-+--++------++++---+++-+-+--+------++-+--++-+-+++-----+-+++++-+------++++-++++-+--+------++--+++++-+-+--+-+++++++++++++++-+--+-+-+---+-+-+++++-++--+-+---++-++--+--+-+++-+-+++++-+--++-+----+++-++-++++-+---+--+-++-++-+-+-+---++-++-+-+----++-++++-----------+++--++++-++-...

output:

Yes
01100000110011010001001010101011001111110000111000101011011111100101100101000111110100000101111110000100001011011111100110000010101101000000000000000101101010111010111111011001010001101100100101110101111101001101000011101101111010001001011011010101000110110101000011011110000000000011100111101101...

result:

ok n=4000

Test #15:

score: 0
Accepted
time: 1449ms
memory: 595456kb

input:

4000
---++-++-+-+----++-++++-----------+++--++++-++-++--+-+--+--+-+-++++--++-++--+++++--++--+-+----+-+---++-+++-+--+-++++++++-++---++++-+--+-+++---+-+--+--+-+--+--++++++-+---++++++-++++----+-+-+-++--+---+--+-+++--++++++-+++-+---+--+-----------++-+++--+++++++--++-+++++--+++-+-+++++++++--+---+++--+-+-...

output:

Yes
10011000110100001001111010000010001110011100110110011000110101010111011000000101100110010000001011000111100101101011011101100000011100001100001100010111001111100100010101101111100100001001100001001001010001001001110011011001001100010000001001001101111111001001110000110101011011110110001100010110...

result:

ok n=4000

Test #16:

score: -100
Wrong Answer
time: 426ms
memory: 82424kb

input:

4000
++-+-------+--++-++-++--++-+++++-++++--+-----++-+--+---++++--+-----++++++---+--+---+------+++-+-----+-+++--+++-+-+-+++-----++---+-+---+-+++++-+--+-++--++-+-----++-+-+---+++-+----++++---++--+-+-++-++-+--++---+++------++-+-++++--+--++-++-+++-++-+--++----++---+-+++-+-+++-++-+--++-++++--++-+-+-+-+-...

output:

No

result:

wrong answer Jury has the answer but participant has not