QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#348934#7857. (-1,1)-Sumpletechenxinyang2006#TL 942ms39548kbC++142.8kb2024-03-09 22:23:212024-03-09 22:23:22

Judging History

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

  • [2024-03-09 22:23:22]
  • 评测
  • 测评结果:TL
  • 用时:942ms
  • 内存:39548kb
  • [2024-03-09 22:23:21]
  • 提交

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

output:


result: