QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#349027#7857. (-1,1)-Sumpletechenxinyang2006#TL 433ms15108kbC++145.0kb2024-03-09 23:07:282024-03-09 23:07:29

Judging History

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

  • [2024-03-09 23:07:29]
  • 评测
  • 测评结果:TL
  • 用时:433ms
  • 内存:15108kb
  • [2024-03-09 23:07:28]
  • 提交

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;
}*/
namespace io {
	const int __SIZE = (1 << 22) + 1;
	char ibuf[__SIZE], *iS, *iT, obuf[__SIZE], *oS = obuf, *oT = oS + __SIZE - 1, __c, qu[55]; int __f, qr, _eof;
	#define Gc() (iS == iT ? (iT = (iS = ibuf) + fread (ibuf, 1, __SIZE, stdin), (iS == iT ? EOF : *iS ++)) : *iS ++)
	inline void flush () { fwrite (obuf, 1, oS - obuf, stdout), oS = obuf; }
	inline void gc (char &x) { x = Gc(); }
	inline void pc (char x) { *oS ++ = x; if (oS == oT) flush (); }
	inline void pstr (const char *s) { int __len = strlen(s); for (__f = 0; __f < __len; ++__f) pc (s[__f]); }
	inline void gstr (char *s) { for(__c = Gc(); __c < 32 || __c > 126 || __c == ' ';)  __c = Gc();
		for(; __c > 31 && __c < 127 && __c != ' '; ++s, __c = Gc()) *s = __c; *s = 0; }
	template <class I> inline bool read (I &x) { _eof = 0;
		for (__f = 1, __c = Gc(); (__c < '0' || __c > '9') && !_eof; __c = Gc()) { if (__c == '-') __f = -1; _eof |= __c == EOF; }
		for (x = 0; __c <= '9' && __c >= '0' && !_eof; __c = Gc()) x = x * 10 + (__c & 15), _eof |= __c == EOF; x *= __f; return !_eof; }
	template <class I> inline void write (I x) { if (!x) pc ('0'); if (x < 0) pc ('-'), x = -x;
		while (x) qu[++ qr] = x % 10 + '0',  x /= 10; while (qr) pc (qu[qr --]); }
	struct Flusher_ {~Flusher_(){flush();}}io_flusher_;
} using io::pc; using io::gc; using io::pstr; using io::gstr; using io::read; using io::write;

int n,s,t;
int G[8005][8005];
bitset <8005> GG[8005],temp,SS[8005],D[8005],curr;
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);
	temp.set();
	temp.reset(s);
	while(!Q.empty()){
		int u = Q.front();
		Q.pop();
		curr = GG[u] & temp;
		while(curr.any()){
			int v = curr._Find_first();
			dis[v] = dis[u] + 1;
			temp.reset(v);curr.reset(v);
			Q.push(v);
		}
	}
	rep(u,s,t) D[u].reset();
	rep(u,s,t) if(dis[u] != inf) D[dis[u]].set(u);
	return dis[t] != inf;
}

int dfs(int u,int flow){
	if(u == t || !flow) return flow;
	int sum = 0,tmp;
//	printf("%d %d\n",u,flow);
	while(cur[u] <= t){
		int v = cur[u];
//		printf("v=%d\n",v);
		SS[u].reset(v);
		cur[u] = SS[u]._Find_next(v);
		tmp = dfs(v,min(flow,G[u][v]));
//		printf("Return value u=%d tmp=%d\n",u,tmp);
		G[u][v] -= tmp;
		G[v][u] += tmp;
		flow -= tmp;
		sum += tmp;
		if(!G[u][v]) GG[u].reset(v);
		GG[v].set(u);
		
		if(!flow || SS[u].none()) return sum;
		
	}
	return sum;
}
int token;
int dinic(){
/*		rep(u,s,t){
			rep(v,s,t) cerr << G[u][v] << " ";
			cerr << endl;
		}
		cerr << endl;*/
	int ans = 0;
	while(bfs()){
//		rep(v,s,t) cerr << dis[v] << " ";
//		cerr << endl;
//		return ans;
//		cerr << "qwq\n";
		rep(u,s,t){
			if(dis[u] != inf) SS[u] = GG[u] & D[dis[u] + 1];
			else SS[u].reset();
			cur[u] = SS[u]._Find_first();
		}
		ans += dfs(s,inf);
/*		rep(u,s,t){
			rep(v,s,t) cerr << G[u][v] << " ";
			cerr << endl;
		}
		cerr << endl;*/
//		return 0;
		token++;
//		cerr <<"qwq\n";
	}		
	cerr << token << endl;
	return ans;
}

int main(){
//	freopen("test.in","r",stdin);
//	freopen("test.out","w",stdout);
	read(n);
	rep(i,1,n){
		gstr(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){
		read(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){
		read(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]) GG[u].set(v);
	}
	if(sum1 != sum2){
		pstr("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){
		pstr("No\n");
		return 0;
	}
	pstr("Yes\n");
	rep(u,1,n){
		rep(v,n + 1,2 * n){
			if(S[u][v - n] == '+') pc('0' + (G[u][v] ^ 1));
			else pc('0' + (G[v][u] ^ 1));
		}
		pc('\n');
	}
	cerr << clock() << endl;
	return 0;
}

详细

Test #1:

score: 100
Accepted
time: 1ms
memory: 3740kb

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

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

input:

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

output:

No

result:

ok n=3

Test #4:

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

input:

1
-
-1
1

output:

No

result:

ok n=1

Test #5:

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

input:

1
-
0
0

output:

Yes
0

result:

ok n=1

Test #6:

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

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

input:

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

output:

Yes
0111010000100110000100011010100111110111000101010110000000000000000000001000100101000010100000010010
1110001110100000000101100100001011101000010010001100010010000010000010110110101111110010111011101111
0011001101111110011000001000010010001000000001000000001101111000011101001000100001000010010100...

result:

ok n=100

Test #8:

score: 0
Accepted
time: 433ms
memory: 15108kb

input:

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

output:

Yes
00101010001000100010010110001000010100100001000000010110011000100001000011001001010010001001000100100010010010010010001001000010000000111001001001000010100100000010001110000001011000001100000001000110101001001000100100010010001001010000010010001010010000000101001000111000000100110100000011010000...

result:

ok n=500

Test #9:

score: -100
Time Limit Exceeded

input:

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

output:


result: