QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#424660#7857. (-1,1)-Sumpletelmeowdn#TL 55ms15828kbC++142.8kb2024-05-29 15:10:212024-05-29 15:10:22

Judging History

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

  • [2024-05-29 15:10:22]
  • 评测
  • 测评结果:TL
  • 用时:55ms
  • 内存:15828kb
  • [2024-05-29 15:10:21]
  • 提交

answer

//Shirasu Azusa 2024.5
#include <bits/stdc++.h>
#define fi first
#define se second
#define eb emplace_back
#define mp make_pair
using namespace std;
typedef long double ld;
typedef long long ll;
typedef unsigned long long ull;
typedef __int128 i128;
template<class T,class S>
bool chmax(T &a,const S b) {return (a<b?a=b,1:0);}
template<class T,class S>
bool chmin(T &a,const S b) {return (a>b?a=b,1:0);}
int popcnt(int x) {return __builtin_popcount(x);}
int popcnt(ll x)  {return __builtin_popcountll(x);}
int topbit(int x) {return (x==0?-1:31-__builtin_clz(x));}
int topbit(ll x)  {return (x==0?-1:63-__builtin_clzll(x));}
int lowbit(int x) {return (x==0?-1:__builtin_ctz(x));}
int lowbit(ll x)  {return (x==0?-1:__builtin_ctzll(x));}

#define int long long
#define rep(i,a,b) for(int i=(a);i<=(b);i++)
#define per(i,a,b) for(int i=(a);i>=(b);i--)
typedef pair<int,int> pii;  
typedef vector<int> vi;
typedef vector<pii> vp;
typedef tuple<int,int,int> tiii;
int read() {
  int x=0,w=1; char c=getchar(); 
  while(!isdigit(c)) {if(c=='-') w=-1; c=getchar();}
  while(isdigit(c)) {x=x*10+(c-'0'); c=getchar();} 
  return x*w;
}

const int N=1e4+5,M=3.5e7+5,inf=(1ll<<31)-1;
int n;
char s[N];

namespace NetF {
	int n,m,s,t,d[N];
	struct edge {int to,nxt,c;} e[M]; int hd[N],cur[N],tot=1;
	void add(int u,int v,int c) {e[++tot]=(edge){v,hd[u],c}; hd[u]=tot;}
	void addh(int u,int v,int c) {add(u,v,c), add(v,u,0);}

	bool bfs() {
		queue<int>q; q.push(s); rep(i,1,n) d[i]=N+1; d[s]=0;
		while(!q.empty()) {
			int u=q.front(); q.pop();
			for(int i=hd[u],v;i;i=e[i].nxt)
				if(e[i].c&&d[v=e[i].to]==N+1) {d[v]=d[u]+1; if(v==t) return 1; q.push(v);}
		} return 0;
	}
	int dfs(int u,int flow) {
		int rest=flow; if(u==t) return flow;
		for(int i=cur[u],v;i&&rest;i=e[i].nxt) {
			if(d[v=e[i].to]!=d[u]+1||!e[i].c) continue;
			cur[u]=i; int use=dfs(v,min(rest,e[i].c));
			if(!use) d[v]=0;
			e[i].c-=use, rest-=use, e[i^1].c+=use;
		} return flow-rest;
	}
	int flow(int S,int T,int ans=0) {
		n=T, s=S, t=T;
		while(bfs()) {
			rep(i,1,n) cur[i]=hd[i]; int res=0;
			while(res=dfs(s,inf)) ans+=res;
		} return ans;
	}
}

signed main() {
	n=read();
	rep(i,1,n) {
		scanf("%s",s+1);
		rep(j,1,n) {
			if(s[j]=='+') NetF::addh(i,j+n,1);
			else NetF::addh(j+n,i,1);
		}
	}
	int S=n*2+1, T=n*2+2, sum1=0, sum2=0, pr=0;
	rep(i,1,n) {
		int x=read();
		if(x>0) NetF::addh(S,i,x), sum1+=x, pr+=x;
		else NetF::addh(i,T,-x), sum1+=x;
	}
	rep(i,1,n) {
		int x=read();
		if(x>0) NetF::addh(i+n,T,x), sum2+=x;
		else NetF::addh(S,i+n,-x), sum2+=x, pr-=x;
	}
	if(sum1!=sum2) return puts("No"), 0;
	int x=NetF::flow(S,T);
	if(x!=pr) return puts("No"), 0;
	puts("Yes"); int tt=0;
	rep(i,1,n) {
		rep(j,1,n) {
			if(NetF::e[(++tt)*2].c==0) putchar('1');
			else putchar('0');
		} puts("");
	}
	return 0;
}

详细

Test #1:

score: 100
Accepted
time: 0ms
memory: 3780kb

input:

3
+-+
-++
+-+
1 1 1
1 -1 3

output:

Yes
001
001
111

result:

ok n=3

Test #2:

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

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

input:

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

output:

No

result:

ok n=3

Test #4:

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

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

input:

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

output:

Yes
00000000010000000100
00000000000010100010
00000000010000000100
00000011010000000100
00100000100101010001
00000000010000000000
00000000000101000101
00000000000000000001
00000000000000000000
00000100001100000001
00000001011100000101
00000000000101001000
10000000000001011000
00000000000001011000
00...

result:

ok n=20

Test #7:

score: 0
Accepted
time: 2ms
memory: 4120kb

input:

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

output:

Yes
1111010100111111010010011010100010100000000000000000000000000000000000000000000011110110100010010011
0110011010111101000110101010100010100000000000000000000000000000000000000000101111110010111011101111
0010001101100110111000000010010010000000000000000000000000000000000000000000001011100010011101...

result:

ok n=100

Test #8:

score: 0
Accepted
time: 55ms
memory: 15828kb

input:

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

output:

Yes
11010101001111100011010001011101011111110001100000010110011010100001000011001101110011001111001101110010011011111010111001000010000000111001001101000010111100100010001110110001010001001100000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000...

result:

ok n=500

Test #9:

score: -100
Time Limit Exceeded

input:

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

output:


result: