QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#348934 | #7857. (-1,1)-Sumplete | chenxinyang2006# | TL | 942ms | 39548kb | C++14 | 2.8kb | 2024-03-09 22:23:21 | 2024-03-09 22:23:22 |
Judging History
answer
#include <bits/stdc++.h>
#define rep(i,j,k) for(int i=(j);i<=(k);i++)
#define per(i,j,k) for(int i=(j);i>=(k);i--)
#define uint unsigned int
#define ll long long
#define ull unsigned long long
#define db double
#define ldb long double
#define pii pair<int,int>
#define pll pair<ll,ll>
#define mkp make_pair
#define eb emplace_back
#define SZ(S) (int)S.size()
//#define mod 998244353
//#define mod 1000000007
#define inf 0x3f3f3f3f
#define linf 0x3f3f3f3f3f3f3f3f
using namespace std;
template <class T>
void chkmax(T &x,T y){
if(x < y) x = y;
}
template <class T>
void chkmin(T &x,T y){
if(x > y) x = y;
}
inline int popcnt(int x){
return __builtin_popcount(x);
}
inline int ctz(int x){
return __builtin_ctz(x);
}
/*ll power(ll p,int k = mod - 2){
ll ans = 1;
while(k){
if(k % 2 == 1) ans = ans * p % mod;
p = p * p % mod;
k /= 2;
}
return ans;
}*/
int n,s,t;
int G[8005][8005];
char S[4005][4005];
int a[4005];
int dis[8005],cur[8005];
queue <int> Q;
int bfs(){
memset(dis,0x3f,sizeof(dis));
dis[s] = 0;
Q.push(s);
while(!Q.empty()){
int u = Q.front();
Q.pop();
rep(v,0,2 * n + 1){
if(G[u][v] && dis[v] > dis[u] + 1){
dis[v] = dis[u] + 1;
Q.push(v);
}
}
}
return dis[t] != inf;
}
int dfs(int u,int flow){
if(u == t || !flow) return flow;
int sum = 0,tmp;
for(int v = cur[u];v <= 2 * n + 1;v = cur[u]){
cur[u] = v + 1;
if(!G[u][v] || dis[v] != dis[u] + 1) continue;
tmp = dfs(v,min(flow,G[u][v]));
G[u][v] -= tmp;
G[v][u] += tmp;
flow -= tmp;
sum += tmp;
if(!flow) return sum;
}
return sum;
}
int dinic(){
int ans = 0;
while(bfs()){
fill(cur,cur + 2 * n + 1,0);
ans += dfs(s,inf);
}
return ans;
}
int main(){
// freopen("test.in","r",stdin);
scanf("%d",&n);
rep(i,1,n){
scanf("%s",S[i] + 1);
rep(j,1,n){
if(S[i][j] == '+') G[i][j + n] = 1;
else G[j + n][i] = 1;
}
}
int sum1 = 0,sum2 = 0;
s = 0;t = 2 * n + 1;
rep(i,1,n){
scanf("%d",&a[i]);
if(a[i] > 0){
G[s][i] = a[i];
sum1 += a[i];
}else{
G[i][t] = -a[i];
sum2 -= a[i];
}
}
rep(i,1,n){
scanf("%d",&a[i]);
a[i] *= -1;
if(a[i] > 0){
G[s][i + n] = a[i];
sum1 += a[i];
}else{
G[i + n][t] = -a[i];
sum2 -= a[i];
}
}
// rep(u,0,2 * n + 1){
// rep(v,0,2 * n + 1) if(G[u][v]) printf("%d->%d %d\n",u,v,G[u][v]);
// }
if(sum1 != sum2){
printf("No\n");
return 0;
}
int ret = dinic();
/* printf("Remaining:\n");
rep(u,0,2 * n + 1){
rep(v,0,2 * n + 1) if(G[u][v]) printf("%d->%d %d\n",u,v,G[u][v]);
}*/
if(ret != sum1){
printf("No\n");
return 0;
}
printf("Yes\n");
rep(u,1,n){
rep(v,n + 1,2 * n){
if(S[u][v - n] == '+') printf("%d",G[u][v] ^ 1);
else printf("%d",G[v][u] ^ 1);
}
printf("\n");
}
return 0;
}
詳細信息
Test #1:
score: 100
Accepted
time: 1ms
memory: 5872kb
input:
3 +-+ -++ +-+ 1 1 1 1 -1 3
output:
Yes 111 001 001
result:
ok n=3
Test #2:
score: 0
Accepted
time: 1ms
memory: 6220kb
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: 5876kb
input:
3 +-+ -++ ++- 1 0 2 2 2 -1
output:
No
result:
ok n=3
Test #4:
score: 0
Accepted
time: 1ms
memory: 5828kb
input:
1 - -1 1
output:
No
result:
ok n=1
Test #5:
score: 0
Accepted
time: 1ms
memory: 5992kb
input:
1 - 0 0
output:
Yes 0
result:
ok n=1
Test #6:
score: 0
Accepted
time: 1ms
memory: 7988kb
input:
20 +-------+-----+++-++ -+-++++----++-++-++- -+++--+---+--+-++--- -+++-+--+----++---+- +++-+-++++++-+-+---+ -++-----+----++++++- +-++--+++++-++-+---- +-+----+---+-+++--+- +++++-+++++----+--+- ------++++---+--++-- ++++--------++++--+- -+-+-++++-+-++-++--+ ---+-++---+-++-++--- +-++++-++----+-+++-- +-+...
output:
Yes 01000001010100111100 00000000010010110010 10000001010001001100 10000001011001000111 11100000100001010000 10000000000001000001 01000000000100000000 01010000000000100110 00000000000000000110 10000000001100000001 00000101010100000101 00000000000000001000 10000000000011001000 00000000100001001000 00...
result:
ok n=20
Test #7:
score: 0
Accepted
time: 12ms
memory: 12440kb
input:
100 ++++-+-+--++++++-+--+--++-+-+--+++++-+++---+-+-+-++-+-+++-------+-++--+-++--+--+++++-++-+---+--+--++ -++--++-+-++++-+---++-+-+-+-+-+-+-+-+--+-+--+--+++---+--+-----+-----+-++-++-+-++++++--+-+++-+++-++++ --+---++-++--++-+++-------+--+-++------+-----+--+----++++++++-+--+++++--++--+-+-+++---+--+++-+...
output:
Yes 0111010000100110000100011010100111110111000101010110000000000000000000001000100101000010100000010010 1110001110100000000101100100001011101000010010001100010010000010000010110110101111110010111011101111 0011001101111110011000001000010010001000000001000000001101111000011101001000100001000010010100...
result:
ok n=100
Test #8:
score: 0
Accepted
time: 942ms
memory: 39548kb
input:
500 --+-+-+-++-----+++--+-+++-+---+-+-------+++--++++++-+--++--+-+-++++-++++--++--+---++--++----++--+---++-++--+-----+-+---++-++++-+++++++---++-++--+-++++-+----++-+++-+++---+--+++-+--++-++--+++++++-+++--+---+---+-+---++-+-+--+-+++-++-----+++-++-+++-+-++--++++++-+-++-+++---++-+++-++----+--+++----++++...
output:
Yes 00101010001000100010010110001000010100100001000000010110011000100001000011001001010010001001000100100010010010010010001001000010000000111001001001000010100100000010001110000001011000001100000001000110101001001000100100010010001001010000010010001010010000000101001000111000000100110100000011010000...
result:
ok n=500
Test #9:
score: -100
Time Limit Exceeded
input:
4000 -++-+-+-+--+-++++---+-++------++---+-+++--+++--+++++++---+-++-+++++++----+---+++-++--++---+-++--+----+---+--++-+-+-+-----+-+---++-++--+---+++-++++-+-----++--++-++---++-+--+++-+--+--+-+-++-+++--++---+++-+-+---+++-++-+-++-+-+++---+++---+-+--++---+-+---+--+++--+----+-+--++---+-----+-+--+----+-+++-...